leetcode回溯+剪枝（排列,组合,子集问题）

清疚 2022-09-04 14:47 188阅读 0赞

排列问题  
46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = \[1,2,3\]  
输出：\[\[1,2,3\],\[1,3,2\],\[2,1,3\],\[2,3,1\],\[3,1,2\],\[3,2,1\]\]

排列问题，采用回溯算法解决，首先将选择过程想成树型结构，并通过回溯，得到所有的结果。  
排列问题需要考虑顺序，此类回溯通用解法，设一个二维数组res保存所有的结果，一个数组path保存当前搜索的路径，depth表示当前树中的深度，对于排列问题，设置一个used数组，记录目前数字是否使用，避免重复使用。

class Solution {
        
        public List<List<Integer>> permute(int[] nums) {
         
        int len=nums.length;
        List<List<Integer>> res=new ArrayList<>();
        if(len==0)return res;
        boolean[] used=new boolean[len];
        List<Integer> path=new ArrayList<>();
        dfs(nums,len,0,path,used,res);
        return res;
        }
        public void dfs(int nums[],int len,int depth,List<Integer> path,boolean[] used,List<List<Integer>> res){
        
            if(depth==len){
        
                //res.add(path);
                //为什么会出现空了。实际上path也确实被加进去了，但是由于Java的特性，下次递归的时候，实际上是又在修改这个path，以及相应的res，致使在最后一次递归复原的时候，把path加入的东西全吐出来了
                res.add(new ArrayList<>(path));//达到最深处，将当前路径添加到结果中
                return;
            }
            for(int i=0;i<len;i++){
        
                if(!used[i]){
        
                    path.add(nums[i]);
                    used[i]=true;
                    dfs(nums,len,depth+1,path,used,res);//递归的执行下一层。
                    used[i]=false;//回溯过程，退回一个。
                    path.remove(path.size()-1);
                }
            }
        }
    }

1.  全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = \[1,1,2\]  
输出：  
\[\[1,1,2\],  
\[1,2,1\],  
\[2,1,1\]\]

与上一题的区别是，这个nums中包含重复的数字，要处理掉重复的结果，进行剪枝。  
先把数字排序，在有序的条件下  
if (i > 0 && nums\[i\] == nums\[i - 1\] && !used\[i - 1\])  
因为数组是有序的，nums\[i-1\]是前一个撤销的数字，如果目前的值和前一个撤销的数字相同，即可进行剪枝（cntinue）。 例如：当前路径中为1，2，前一个撤销的数字为3；说明1，2，3开头的排列都已经找完了，如果nums\[i\]还等于3，即可剪枝跳过，去掉重复的值。

class Solution {
        
        public List<List<Integer>> permuteUnique(int[] nums) {
        
        int len=nums.length;
        List<List<Integer>> res=new ArrayList<>();
        if(len==0)return res;
        Arrays.sort(nums);//先经过排序，后续剪枝的num[i-1]才能保证是上一步撤销的值。
        boolean[] used=new boolean[len];
        // 使用 Deque 是 Java 官方 Stack 类的建议
        Deque<Integer> path = new ArrayDeque<>(len);
        dfs(nums,len,0,path,used,res);
        return res;
        }
        public void dfs(int nums[],int len,int depth,Deque<Integer> path,boolean[] used,List<List<Integer>> res){
        
            if(depth==len){
        
                res.add(new ArrayList<>(path));
                return;
            }
            for(int i=0;i<len;i++){
        
                if (used[i]) {
        
                    continue;
                }
                // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
                // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
        
                    continue;
                }
                path.addLast(nums[i]);
                used[i] = true;
                dfs(nums, len, depth + 1, path, used, res);
                // 回溯部分的代码，和 dfs 之前的代码是对称的
                used[i] = false;
                path.removeLast();
            }
    }}

组合问题  
39. 组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

输入: candidates = \[2,3,6,7\], target = 7  
输出: \[\[7\],\[2,2,3\]\]

组合问题区别于排列，不使用used\[\]数组，如果使用used数组，当选择了1后，再选择2；如果选择了2，used\[1\]还是0，可以被选择，所以会产生两个重复的组合。  
所以组合不使用used数组，而是用begin，在数组有序的情况下，不会选择前面的数字。  
例如path\[1,2\]，begin=2，不会再去寻找前面的值  
和为7，根节点为7，尝试减去给定数组的各个值，如果最后在叶子节点中能够减为0，则该路径上的值的和为target。

class Solution {
        
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        int len=candidates.length;
        List<List<Integer>> res=new ArrayList<>();
        Deque<Integer> path=new ArrayDeque<>(len);
        Arrays.sort(candidates);//一定要排序
        if(len==0)return res;
        dfs(candidates,len,0,path,res,target);//初始begin起始点为0
        return res;
        }
        public void dfs(int[] nums, int len, int begin, Deque<Integer> path, List<List<Integer>> res,int target){
        
            if(target==0){
        
                res.add(new ArrayList<>(path));
                return;
            }
            for(int i=begin;i<len;i++){
        
                if(target-nums[i]<0){
        //剪枝条件
                    break;
                }
                path.addLast(nums[i]);
                dfs(nums,len,i,path,res,target-nums[i]);
                path.removeLast();
            }
        }
    }

1.  组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。  
输入: candidates = \[10,1,2,7,6,1,5\], target = 8,  
输出:  
\[  
\[1,1,6\],  
\[1,2,5\],  
\[1,7\],  
\[2,6\]  
\]  
与上一题的区别是每个数字只能使用一次。  
递归的dfs中，传递的begin值为i+1，因为每个元素只能使用一次。

public class Solution {
        
    
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
            int len = candidates.length;
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) {
        
                return res;
            }
    
            // 关键步骤
            Arrays.sort(candidates);
    
            Deque<Integer> path = new ArrayDeque<>(len);
            dfs(candidates, len, 0, target, path, res);
            return res;
        }
        private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
        
            if (target == 0) {
        
                res.add(new ArrayList<>(path));
                return;
            }
            for (int i = begin; i < len; i++) {
        
                if (target - candidates[i] < 0) {
        
                    break;
                }
                if (i > begin && candidates[i] == candidates[i - 1]) {
        
                    continue;
                }//数组中有多个相同数字，保证不产生重复的结果。
                path.addLast(candidates[i]);
                // 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
                dfs(candidates, len, i + 1, target - candidates[i], path, res);
                path.removeLast();
            
            }
        }
    
    
    }

1.  组合

给定两个整数 n 和 k，返回范围 \[1, n\] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。  
输入：n = 4, k = 2  
输出：  
\[  
\[2,4\],  
\[3,4\],  
\[2,3\],  
\[1,2\],  
\[1,3\],  
\[1,4\],  
\]

也是一个不能重复选择的组合，多了个参数k，找到指定的个数的即可。

class Solution {
        
        public List<List<Integer>> combine(int n, int k) {
        
            int[] candidates=new int[n+1];
            for(int i=1;i<=n;i++){
        
                candidates[i]=i;
            }
            int len = candidates.length;
            List<List<Integer>> res = new ArrayList<>();
            if (len == 0) {
        
                return res;
            }
            Deque<Integer> path = new ArrayDeque<>(len);
            dfs(candidates, len, 1, path, res,k,0);
            return res;
        }
        private void dfs(int[] candidates, int len, int begin,Deque<Integer> path, List<List<Integer>> res,int k,int depth) {
        
            if(depth==k){
        
                res.add(new ArrayList<>(path));
                return;
            }
            for(int i=begin;i<len;i++){
        
                path.addLast(candidates[i]);
                dfs(candidates, len, i + 1, path, res,k,depth+1);
                path.removeLast();
            }
        }
    }

1.  子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。  
本质也是组合，不过函数每次执行都把当前路径加到结果中，保证子集都考虑。

class Solution {
        
        public List<List<Integer>> subsets(int[] nums) {
        
            int len = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            // 关键步骤
            Arrays.sort(nums);
            Deque<Integer> path = new ArrayDeque<>(len);
            dfs(res,nums,path,0,len);
            return res;
        }
        private void dfs(List<List<Integer>> res,int[] nums,Deque<Integer> path,int begin,int length) {
        
            res.add(new ArrayList<>(path));
            for(int i=begin;i<length;i++){
        
                path.addLast(nums[i]);
                dfs(res,nums,path,i+1,length);
                path.removeLast();
            }
        }
    }

1.  子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

与上一道题的区别是，nums中可能包含重复元素。与之前的组合类似，需要进行剪枝，如果nums\[i\]==nums\[i-1\]就进行剪枝。

class Solution {
        
        public List<List<Integer>> subsetsWithDup(int[] nums) {
        
          int len = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            // 关键步骤
            Arrays.sort(nums);
            Deque<Integer> path = new ArrayDeque<>(len);
            dfs(res,nums,path,0,len);
            return res;
        }
        private void dfs(List<List<Integer>> res,int[] nums,Deque<Integer> path,int begin,int length) {
        
            res.add(new ArrayList<>(path));
            for(int i=begin;i<length;i++){
        
                if(i>begin&&nums[i]==nums[i-1]){
        
                   continue;
                }
                path.addLast(nums[i]);
                dfs(res,nums,path,i+1,length);
                path.removeLast();
            }
    }
    }

1.  排列序列

给出集合 \[1,2,3,…,n\]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
    "132"
    "213"
    "231"
    "312"
    "321"

给定 n 和 k，返回第 k 个排列。

如果采用回溯法解决，很容易超时，所以要采用正确的剪枝方法，我的做法是，本题求第k个，当搜索到第k个之后就直接结束回溯，不在继续后面的，但是这样也很浪费时间。  
把递归函数设置为布尔型，把递归函数的执行放到if条件判断中，保证执行

class Solution {
        
        boolean[] def;
        StringBuilder res;
        int count;
        int k;
        int n;
        public String getPermutation(int n, int k) {
        
            this.k = k;
            this.n = n;
            def = new boolean[n+1]; // 哈希表做访问标记
            count++;
            res = new StringBuilder(); // 可变res
            dfs(0);
            return res.toString();
        }
        boolean dfs(int depth){
        
            if(depth == n){
        
                if(count == k){
         // 说明已经找到了第 k 个，直接返回true，方便剪枝
                    return true;
                }
                else{
        
                    ++count; // 还没找到第 k 个，所以count自增，并且返回false。
                    return false;
                }
            }
            for(int i = 1;i <= n;++i){
        
                if(def[i]) continue; // 已访问元素直接略过，i从1开始保证了k个结果的大小顺序
                def[i] = true; // 未访问元素先做标记
                res.append(i); 
                if(dfs(depth+1)) return true; // 大剪枝，也就是说找到了元素，此后就不必再找了
                res.deleteCharAt(res.length()-1); // 每次删除res的最后一个字符，回溯。
                def[i] = false; // 恢复未访问标记
            }
            return false;
        }
    }

看了回溯的高效解法，当搜索进行到某一层时，先查看该点下面一共有多少种可能，如果小于给定的k，可以直接进行剪枝，因为就算把下面的路径都搜索出来，也达不到k。

import java.util.Arrays;
    
    public class Solution {
        
    
        private boolean[] used;
    
        /**
         * 阶乘数组
         */
        private int[] factorial;
    
        private int n;
        private int k;
    
        public String getPermutation(int n, int k) {
        
            this.n = n;
            this.k = k;
            calculateFactorial(n);
    
           
            used = new boolean[n + 1];
            Arrays.fill(used, false);
    
            StringBuilder path = new StringBuilder();
            dfs(0, path);
            return path.toString();
        }
    
    
        /**
         * @param index 在这一步之前已经选择了几个数字，其值恰好等于这一步需要确定的下标位置
         * @param path
         */
        private void dfs(int index, StringBuilder path) {
        
            if (index == n) {
        
                return;
            }
    
            // 计算还未确定的数字的全排列的个数，第 1 次进入的时候是 n - 1
            int cnt = factorial[n - 1 - index];
            for (int i = 1; i <= n; i++) {
        
                if (used[i]) {
        
                    continue;
                }
                if (cnt < k) {
        
                    k -= cnt;//当前点之下可能的结果达不到k，直接换下一个，并从k中减去。
                    continue;
                }
                path.append(i);
                used[i] = true;
                dfs(index + 1, path);
                // 注意 1：不可以回溯（重置变量），算法设计是「一下子来到叶子结点」，没有回头的过程
                // 注意 2：这里要加 return，后面的数没有必要遍历去尝试了
                return;
            }
        }
    
        /**
         * 计算阶乘数组
         *
         * @param n
         */
        private void calculateFactorial(int n) {
        
            factorial = new int[n + 1];
            factorial[0] = 1;
            for (int i = 1; i <= n; i++) {
        
                factorial[i] = factorial[i - 1] * i;
            }
        }
    }

1.  字母大小写全排列

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例：  
输入：S = “a1b2”  
输出：\[“a1b2”, “a1B2”, “A1b2”, “A1B2”\]

输入：S = “3z4”  
输出：\[“3z4”, “3Z4”\]

输入：S = “12345”  
输出：\[“12345”\]  
此题虽说是字符串的排列，但实际上字母的顺序并不能改变，不能用used数组，应该用begin设置初始值。  
遇到数字，直接进行递归回溯，如果是字母，先将其大写字母进行递归回溯，再将其小写字母递归回溯即可。

class Solution {
        
    
        private List<String> res = new ArrayList<>();
        public List<String> letterCasePermutation(String s) {
        
    
            StringBuilder sb = new StringBuilder();
    
            backtrack(s, 0, sb);
            return res;
        }
    
        public void backtrack(String s, int start, StringBuilder sb) {
        
    
            if (sb.length() == s.length()) {
        
    
                res.add(sb.toString());
                return ;
            }
    
            for (int i=start;i<s.length();i++) {
        
    
                char c = s.charAt(i);
    
                if (Character.isDigit(c)) {
        
    
                    sb.append(c);
                    backtrack(s, i + 1, sb);
                    sb.deleteCharAt(sb.length() - 1); // 撤销选择
                } else {
        
    
                    char A = Character.toUpperCase(c);//大写执行一遍
                    sb.append(A);
                    backtrack(s, i + 1, sb);
                    sb.deleteCharAt(sb.length() - 1);
    
                    char a = Character.toLowerCase(c);//小写执行一遍
                    sb.append(a);
                    backtrack(s, i + 1, sb);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
    }