回朔法总结之组合,全排列,子集
1 子集
给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0, new ArrayList<>());
return res;
}
public void backtrack(int[] nums, int index, List<Integer> track){
res.add(new ArrayList<>(track));
for (int i = index; i < nums.length; i++){
track.add(nums[i]);
backtrack(nums, i+1, track);
track.remove(track.size()-1);
}
}
}
2 子集二
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums == null || nums.length == 0) return ans;
Arrays.sort(nums);
dfs(0, nums);
return ans;
}
private void dfs(int i, int[] nums) {
if (ans.contains(tmp)) return;
ans.add(new ArrayList<>(tmp));
for (int j = i; j < nums.length; j++) {
tmp.add(nums[j]);
dfs(j+1, nums);
tmp.remove(tmp.size()-1);
}
}
}