子集问题概述

78. 子集

求子集问题和77.组合 (opens new window)和131.分割回文串 (opens new window)又不一样了。
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。
那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
可以不写递归终止条件，因为要遍历整个树

  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList<>();
  3.     List<Integer> path = new ArrayList<>();
  4.     public List<List<Integer>> subsets(int[] nums) {
  5.         backtrack(nums, 0);
  6.         return res;
  7.     }
  9.     public void backtrack(int[] nums, int startIndex){
  10.         res.add(new ArrayList<>(path));
  11.         if (path.size() == nums.length) {
  12.             return ;
  13.         }
  14.         for (int i = startIndex; i < nums.length; ++i) {
  15.             path.add(nums[i]);
  16.             backtrack(nums, i + 1);
  17.             path.remove(path.size() - 1);
  18.         }
  19.     }
  20. }

90. 子集 II

「可能包含重复元素」
startIndex + used[]

  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList<>();
  3.     List<Integer> path = new ArrayList<>();
  4.     public List<List<Integer>> subsetsWithDup(int[] nums){
  5.         Arrays.sort(nums);
  6.         backtrack(nums, 0, new boolean[nums.length]);
  7.         return res;
  8.     }
  10.     public void backtrack(int[] nums, int startIndex, boolean[] used){
  11.         res.add(new ArrayList<>(path));
  12.         if (path.size() == nums.length) {
  13.             return ;
  14.         }
  15.         for (int i = startIndex; i < nums.length; ++i) {
  16.             if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
  17.                 continue;
  18.             }
  19.             path.add(nums[i]);
  20.             used[i] = true;
  21.             backtrack(nums, i + 1, used);
  22.             used[i] = false;
  23.             path.remove(path.size() - 1);
  24.         }
  25.     }
  26. }

491. 递增子序列

有重复元素，但是不能排序，不然就破坏了原来的递增关系，因此不能使用boolean uesd[]来去重，我们使用数组哈希，来判断这个数在当前层是否使用过。如果元素数值范围巨大，则使用HashMap代替数组哈希

  1. class Solution {
  2.     List<List<Integer>> res = new ArrayList<>();
  3.     List<Integer> path = new ArrayList<>();
  4.     public List<List<Integer>> findSubsequences(int[] nums){
  5.         backtrack(nums, 0);
  6.         return res;
  7.     }
  9.     public void backtrack(int[] nums, int startIndex){
  10.         if (path.size() > 1) { //要求至少两个元素
  11.             res.add(new ArrayList<>(path));
  12.         }
  13.         if (path.size() == nums.length) {
  14.             return;
  15.         }
  16.         int[] used = new int[201];//因为元素范围是-100～100，共201个元素
  17.         for (int i = startIndex; i < nums.length; ++i) {
  18.             //不满足递增
  19.             if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)){
  20.                 continue;
  21.             }
  22.             //当前数字使用过了
  23.             if(used[nums[i] + 100] == 1){
  24.                 continue;
  25.             }
  26.             used[nums[i] + 100] = 1;
  27.             path.add(nums[i]);
  28.             backtrack(nums, i + 1);
  29.             path.remove(path.size() - 1);
  30.         }
  31.     }
  32. }