二刷代码随想录|Java版|回溯算法3|子集问题

习题

2.3 子集问题

就是组合过程收集path。就像是代码随想录里说得那样，组合和分割问题就是收集叶子结点，子集问题就是收集每一个节点。
有涉及到同层重复元素的问题。
先排序，后再for循环里处理相同数值跳过。
设置函数内的used。
还可以用HashSet，Map
HashSet：

//创建
HashSet<Integer> hs = new HashSet<>();
//判断
|| hs.contains(nums[i])
//修改
hs.add(nums[i]);

Map：

//创建
HashMap<Integer,Integer> map = new HashMap<>();
//判断
if ( map.getOrDefault( nums[i],0 ) >=1 ){//返回 key 相映射的的 value，如果给定的 key 在映射关系中找不到，则返回指定的默认值。continue;
}            
//修改
map.put(nums[i],map.getOrDefault( nums[i],0 )+1);

2.3.1 78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
还是要画回溯树比较快，需要startIdx，结束条件就是与length比较。

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> path = new ArrayList<Integer>();private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList<>(path));for(int i=startIdx; i<nums.length; i++){path.add(nums[i]);Backtracing(nums, i+1);path.removeLast();}       }public List<List<Integer>> subsets(int[] nums) {ans.clear();path.clear();Backtracing(nums, 0);return ans;}
}

2.3.2 90. 子集 II

涉及同层重复元素的排除。
还是要画回溯树比较好理解。
还记得就是先排序，后再for循环里处理相同数值跳过。

class Solution {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> path = new ArrayList<Integer>();private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList<>(path));for(int i=startIdx; i<nums.length; i++){if(i!=startIdx&&nums[i]==nums[i-1]){continue;}path.add(nums[i]);Backtracing(nums, i+1);path.removeLast();}  }public List<List<Integer>> subsetsWithDup(int[] nums) {ans.clear();path.clear();Arrays.sort(nums);Backtracing(nums, 0);return ans;}
}

class Solution {List<List<Integer>> ans = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果boolean[] used;private void Backtracing(int[] nums, int startIdx){ans.add(new ArrayList<>(path));if (startIdx >= nums.length){return;}for (int i = startIdx; i < nums.length; i++){if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){continue;}path.add(nums[i]);used[i] = true;Backtracing(nums, i + 1);path.removeLast();used[i] = false;}}public List<List<Integer>> subsetsWithDup(int[] nums) {if (nums.length == 0){ans.add(path);return ans;}Arrays.sort(nums);used = new boolean[nums.length];Backtracing(nums, 0);return ans;}
}

2.3.3 491.递增子序列

示例 1：至少两个元素
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
想要用used来，可是有负数，我该怎么处理？有说范围-100,100，所以可以用数组哦。

class Solution {List<List<Integer>> ans = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();private void Backtracing(int[] nums, int startIdx){if(path.size()>=2){ans.add(new ArrayList<>(path));}if (startIdx >= nums.length){return;}int[] used = new int[201];for (int i = startIdx; i < nums.length; i++){if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || (used[nums[i] + 100] == 1)) continue;used[nums[i] + 100] = 1;path.add(nums[i]);Backtracing(nums, i + 1);path.removeLast();}}public List<List<Integer>> findSubsequences(int[] nums) {if (nums.length == 0){ans.add(path);return ans;}Backtracing(nums, 0);return ans;}
}

还可以用HashSet，Map
HashSet：

//创建
HashSet<Integer> hs = new HashSet<>();
//判断
|| hs.contains(nums[i])
//修改
hs.add(nums[i]);

Map：

//创建
HashMap<Integer,Integer> map = new HashMap<>();
//判断
if ( map.getOrDefault( nums[i],0 ) >=1 ){continue;
}            
//修改
map.put(nums[i],map.getOrDefault( nums[i],0 )+1);