78. 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]解：标准dfs深度优先回溯算法。回溯算法的基本形式是“递归+循环”，正因为循环中嵌套着递归，递归中包含循环，这才使得回溯比一般的递归和单纯的循环更难理解，其实我们熟悉了它的基本形式，就会觉得这样的算法难度也不是很大。原数组中的每个元素有两种状态：存在和不存在。
- 外层循环逐一往中间集合 tmp 中加入元素 nums[i]，使这个元素处于存在状态
- 开始递归，递归中携带加入新元素的 tmp，并且下一次循环的起始是 i 元素的下一个，因而递归中更新 i 值为 i + 1
- 将这个从中间集合 tmp 中移除，使该元素处于不存在状态
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> tmp = new ArrayList<Integer>();
dfs(result, tmp, nums, 0);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> tmp, int[] nums, int index) {
result.add(new ArrayList<Integer>(tmp));
for (int i = index; i < nums.length; i++) {
tmp.add(nums[i]);
dfs(result, tmp, nums, i + 1);
tmp.remove(tmp.size() - 1);
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018-06-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读