第13章 回溯法
组合问题
剑指offerⅡ79：所有子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
写法一：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new LinkedList<>();
if(nums.length==0){
return ans;
}
dfs(nums,0,new LinkedList<>(),ans);
System.out.println(ans.toString());
return ans;
}
private void dfs(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> ans){
if(index==nums.length){
ans.add(new LinkedList<>(subset));
return;
}
subset.add(nums[index]); //先选择下标为index的数
dfs(nums,index+1, subset, ans); //在选择index的情况下，确定index+1的选择情况
subset.removeLast(); //不选择下标为index的数
dfs(nums,index+1, subset, ans); //在不选择index的情况下，确定index+1的选择情况
}
}
大约 8 分钟