dfs处理排列组合子集切割问题.pdf

46. 全排列

  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList<>();
  3.     List<Integer> path = new ArrayList<>();
  4.     public List<List<Integer>> permute(int[] nums) {
  5.         dfs(0, nums, 0);
  6.         return res;
  7.     }
  9.     void dfs(int u, int[] nums, int st) {
  10.         if (u == nums.length) {
  11.             res.add(new ArrayList<>(path));
  12.             return;
  13.         }
  15.         for (int i = 0; i < nums.length; i++) {
  16.             if ((st >> i & 1) == 1)
  17.                 continue;
  18.             path.add(nums[i]);
  19.             dfs(u + 1, nums, st | (1 << i));
  20.             path.remove(path.size() - 1);
  21.         }
  22.     }
  23. }

当然path也可以用整型数组代替 st也能用boolean数组代替

47. 全排列 II

  1. // 多了排序 + 判重的步骤
  2. class Solution {
  3.     List<List<Integer>> res = new ArrayList<>();
  4.     List<Integer> path = new ArrayList<>();
  5.     public List<List<Integer>> permuteUnique(int[] nums) {
  6.         Arrays.sort(nums);
  7.         dfs(0, nums, 0);
  8.         return res;
  9.     }
  11.     void dfs(int u, int[] nums, int st) {
  12.         if (u == nums.length) {
  13.             res.add(new ArrayList<>(path));
  14.             return;
  15.         }
  17.         for (int i = 0; i < nums.length; i++) {
  18.             if ((st >> i & 1) == 1 || (i > 0 && nums[i] == nums[i - 1] && (st >> (i - 1) & 1) == 0))
  19.                 continue;
  20.             path.add(nums[i]);
  21.             dfs(u + 1, nums, st | (1 << i));
  22.             path.remove(path.size() - 1);
  23.         }
  24.     }
  25. }

77. 组合

  1. // 方法1 dfs
  2. class Solution {
  3.     List<List<Integer>> res = new ArrayList<>();
  4.     List<Integer> path = new ArrayList<>();
  5.     public List<List<Integer>> combine(int n, int k) {
  6.         dfs(1, 1, n, k);
  7.         return res;
  8.     }
  10.     void dfs(int u, int start, int n, int m) {
  11.         if (u == m + 1) {
  12.             res.add(new ArrayList<>(path));
  13.             return;
  14.         }
  16.         for (int i = start; i + m - u <= n; i++) {
  17.             path.add(i);
  18.             dfs(u + 1, i + 1, n, m);
  19.             path.remove(path.size() - 1);
  20.         }
  21.     }
  23. }
  1. // 方法2：二进制枚举
  2. class Solution {
  3.     List<List<Integer>> res = new ArrayList<>();
  5.     public List<List<Integer>> combine(int n, int k) {
  6.         for (int i = 0; i < 1 << n; i++) {
  7.             if (Integer.bitCount(i) != k) continue;
  8.             List<Integer> path = new ArrayList<>();
  9.             for (int j = 0; j < n; j++) {
  10.                 if ((i >> j & 1) == 1) {
  11.                     path.add(j + 1);
  12.                 }
  13.             }
  14.             res.add(path);
  15.         }
  16.         return res;
  17.     }
  19. }

二进制枚举不能保证输出为字典序

40. 组合总和 II

  1. // 排序 + 按层剪枝 + 可行性剪枝
  2. class Solution {
  3.     List<List<Integer>> res = new ArrayList<>();
  4.     List<Integer> path = new ArrayList<>();
  5.     public List<List<Integer>> combinationSum2(int[] candidates, int target) { 
  6.         Arrays.sort(candidates);
  7.         dfs(0, candidates, 0, target);
  8.         return res;
  9.     }
  11.     void dfs(int u, int[] candidates, int sum, int target) {
  12.         if (sum == target) {
  13.             res.add(new ArrayList<>(path));
  14.             return;
  15.         }
  17.         for (int i = u; i < candidates.length && sum + candidates[i] <= target; i++) {
  18.             if (i > u && candidates[i] == candidates[i - 1])
  19.                 continue;
  20.             path.add(candidates[i]);
  21.             dfs(i + 1, candidates, sum + candidates[i], target);
  22.             path.remove(path.size() - 1);
  23.         }
  24.     }
  27. }

78. 子集

  1. 方法1：二进制枚举
  2. class Solution {
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         int n = nums.length;
  6.         List<List<Integer>> res = new ArrayList<>();
  8.         for (int i = 0; i < 1 << n; i++) {
  9.             List<Integer> path = new ArrayList<>();
  10.             for (int j = 0; j < n; j++) {
  11.                 if ((i >> j & 1) == 1)
  12.                     path.add(nums[j]);
  13.             }
  14.             res.add(path);
  15.         }
  16.         return res;
  17.     }
  18. }
  1. // 方法2 dfs
  2. class Solution {
  3.     List<List<Integer>> res = new ArrayList<>();
  4.     List<Integer> path = new ArrayList<>();
  5.     public List<List<Integer>> subsets(int[] nums) {
  6.         dfs(0, nums);
  7.         return res;
  8.     }
  9.     void dfs(int startIndex, int[] nums) {
  10.         res.add(new ArrayList<>(path));
  12.         for (int i = startIndex; i < nums.length; i++) {
  13.             path.add(nums[i]);
  14.             dfs(i + 1, nums);
  15.             path.remove(path.size() - 1);
  16.         }
  17.     }
  18. }

90. 子集 II

  1. // 方法一 二进制枚举
  2. class Solution {
  3.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  4.         Arrays.sort(nums);
  5.         int n = nums.length;
  6.         List<List<Integer>> res = new ArrayList<>();
  9.         label: for (int i = 0; i < 1 << n; i++) {
  10.             List<Integer> path = new ArrayList<>();
  11.             for (int j = 0; j < n; j++) {
  12.                 if ((i >> j & 1) == 1) {
  13.                     if (j > 0 && nums[j] == nums[j - 1] && (i >> (j - 1) & 1) == 0)
  14.                         continue label;
  15.                     path.add(nums[j]);
  16.                 }
  17.             }
  18.             res.add(path);
  19.         }
  20.         return res;
  21.     }
  22. }
  1. // 方法2 排序 + 按层判重
  2. class Solution {
  3.     List<List<Integer>> res = new ArrayList<>();
  4.     List<Integer> path = new ArrayList<>();
  5.     int n;
  6.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  7.         n = nums.length;
  8.         Arrays.sort(nums);
  10.         dfs(0, nums);
  11.         return res;
  12.     }
  14.     void dfs(int u, int[] nums) {
  15.         res.add(new ArrayList<>(path));
  17.         for (int i = u; i < n; i++) {
  18.             if (i > u && nums[i] == nums[i - 1])
  19.                 continue;
  20.             path.add(nums[i]);
  21.             dfs(i + 1, nums);
  22.             path.remove(path.size() - 1);
  23.         }
  24.     }
  25. }
  1. // 方法3 排序 + 判重数组(判重数组也可以用二进制数记录)
  2. class Solution {
  3.     List<List<Integer>> res = new ArrayList<>();
  4.     List<Integer> path = new ArrayList<>();
  5.     int n;
  6.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  7.         n = nums.length;
  8.         Arrays.sort(nums);
  9.         boolean[] st = new boolean[n];
  10.         dfs(0, nums, st);
  11.         return res;
  12.     }
  14.     void dfs(int u, int[] nums, boolean[] st) {
  15.         res.add(new ArrayList<>(path));
  17.         for (int i = u; i < n; i++) {
  18.             if (i > u && nums[i] == nums[i - 1] && !st[i - 1])
  19.                 continue;
  20.             path.add(nums[i]);
  21.             st[i] = true;
  22.             dfs(i + 1, nums, st);
  23.             st[i] = false;
  24.             path.remove(path.size() - 1);
  25.         }
  26.     }
  27. }
  1. // 方法4 排序 + 层内Set
  2. class Solution {
  3.     List<List<Integer>> res = new ArrayList<>();
  4.     List<Integer> path = new ArrayList<>();
  5.     int n;
  6.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  7.         n = nums.length;
  8.         Arrays.sort(nums);
  9.         dfs(0, nums);
  10.         return res;
  11.     }
  13.     void dfs(int u, int[] nums) {
  14.         res.add(new ArrayList<>(path));
  16.         Set<Integer> set = new HashSet<>();
  17.         for (int i = u; i < n; i++) {
  18.             if (set.contains(nums[i]))
  19.                 continue;
  20.             set.add(nums[i]);
  21.             path.add(nums[i]);
  22.             dfs(i + 1, nums);
  23.             path.remove(path.size() - 1);
  24.         }
  25.     }
  26. }