【LeetCode】回溯问题：排列与组合

古城微笑少年丶 2022-10-29 09:12 217阅读 0赞

### 排列问题 ###

#### [46. 全排列][46.] ####

难度中等1120收藏分享切换为英文接收动态反馈

给定一个 **没有重复** 数字的序列，返回其所有可能的全排列。

**示例:**

输入: [1,2,3]
    输出:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

**题解**

class Solution { 
        public List<List<Integer>> permute(int[] nums) { 
            List<List<Integer>> res = new ArrayList<>();
            LinkedList<Integer> path = new LinkedList<>();
            boolean[] bitmap = new boolean[nums.length];
    
            func(nums , bitmap , path , res);
            return res;
        }
    
        void func(int[] nums , boolean[] bitmap , LinkedList<Integer> path , List<List<Integer>> res){ 
            if(path.size() == nums.length){ 
                List<Integer> list = new ArrayList<>();
                for(Integer i : path){ 
                    list.add(i);
                }
                res.add(list);
                return;
            }
    
            for(int i = 0 ; i < bitmap.length ; i ++){ 
                if(! bitmap[i]){ 
                    bitmap[i] = true;
                    path.addLast(nums[i]);
    
                    func(nums , bitmap , path , res);
    
                    path.removeLast();
                    bitmap[i] = false;
                }
            }
        }
    }

#### [47. 全排列 II][47. _ II] ####

难度中等586收藏分享切换为英文接收动态反馈

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

**示例 1：**

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

**示例 2：**

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

**题解**

class Solution { 
        public List<List<Integer>> permuteUnique(int[] nums) { 
            List<List<Integer>> res = new ArrayList<>();
            LinkedList<Integer> path = new LinkedList<>();
            boolean[] bitmap = new boolean[nums.length];
    
            func(nums , bitmap , path , res);
            return res;
        }
    
        void func(int[] nums , boolean[] bitmap , LinkedList<Integer> path , List<List<Integer>> res){ 
            if(path.size() == nums.length){ 
                List<Integer> list = new ArrayList<>();
                for(Integer i : path){ 
                    list.add(i);
                }
                res.add(list);
                return;
            }
    
            Set<Integer> distinct = new HashSet<>();
            for(int i = 0 ; i < bitmap.length ; i ++){ 
                if(! bitmap[i] && !distinct.contains(nums[i])){ 
                    bitmap[i] = true;
                    path.addLast(nums[i]);
    
                    func(nums , bitmap , path , res);
    
                    path.removeLast();
                    bitmap[i] = false;
                    distinct.add(nums[i]);
                }
            }
        }
    }

### 组合问题 ###

*  核心就是不能重复（其实任何不重复的问题都是通过后面不可以使用前面的来保证）
 *  即状态转移时，idx 不能转移到 idx - 1

对于剪枝

*  对于状态转移来说，终止状态转移无非两种情况，一种是不满足状态转移所要求的条件，一种是到了状态转移的终点（比如遍历完了所有元素或者遍历到了要求的终点）
 *  一般剪掉的是不满足条件那一部分

#### [77. 组合][77.] ####

难度中等488收藏分享切换为英文接收动态反馈

给定两个整数 *n* 和 *k*，返回 1 … *n* 中所有可能的 *k* 个数的组合。

**示例:**

输入: n = 4, k = 2
    输出:
    [
      [2,4],
      [3,4],
      [2,3],
      [1,2],
      [1,3],
      [1,4],
    ]

**题解**

class Solution { 
        public List<List<Integer>> combine(int n, int k) { 
            List<List<Integer>> res = new ArrayList<>();
            LinkedList<Integer> path = new LinkedList<>();
    
            func(1 , n , k , path , res);
            return res;
        }
    
        void func(int idx , int n , int remain , LinkedList<Integer> path ,List<List<Integer>> res){ 
            if(remain == 0){ 
                List<Integer> l = new ArrayList<>();
                for(Integer i : path){ 
                    l.add(i);
                }
                res.add(l);
                return;
            }
    
            if(idx == n + 1){ 
                return;
            }
    
            for(int i = idx ; i <= n ; i ++){ 
                path.addLast(i);
                func(i + 1 , n , remain - 1 , path ,res);
                path.removeLast();
            }
        }
    }

#### [39. 组合总和][39.] ####

难度中等1154收藏分享切换为英文接收动态反馈

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

`candidates` 中的数字可以无限制重复被选取。

**说明：**

*  所有数字（包括 `target`）都是正整数。
 *  解集不能包含重复的组合。

**示例 1：**

输入：candidates = [2,3,6,7], target = 7,
    所求解集为：
    [
      [7],
      [2,2,3]
    ]

**示例 2：**

输入：candidates = [2,3,5], target = 8,
    所求解集为：
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]

**题解**

class Solution { 
        public List<List<Integer>> combinationSum(int[] candidates, int target) { 
            List<List<Integer>> res = new ArrayList<>();
            LinkedList<Integer> path = new LinkedList<>();
            
            func(candidates , 0 , target , path , res);
            return res;
        }
    
        void func(int[] candidates , int idx, int remain , LinkedList<Integer> path , List<List<Integer>> res){ 
            if(remain == 0){ 
                res.add(new ArrayList(path));
                return ;
            }
    
            for(int i = idx ;i < candidates.length ; i ++){ 
                if(remain - candidates[i] >= 0){ 
                    path.addLast(candidates[i]);
                    func(candidates , i, remain - candidates[i] , path ,res);
                    path.removeLast();
                }
            }
        }
    }

[46.]: https://leetcode-cn.com/problems/permutations/
[47. _ II]: https://leetcode-cn.com/problems/permutations-ii/
[77.]: https://leetcode-cn.com/problems/combinations/
[39.]: https://leetcode-cn.com/problems/combination-sum/