【LeetCode】78 - 子集

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

解题思路

回溯法

设置一个头指针int first和一个当前列表ArrayList<Integer> curList，每次（递归地）进入回溯方法时，先将当前列表curList加入结果列表，再对数组从头指针first到尾部进行遍历，每次遍历都分三步：

在当前列表curList加入当前指针对应的数组的元素nums[i]
（递归地）处理剩下的i+1到nums.length - 1个元素
回溯，删掉刚才用过的元素（尾部元素）

Java 实现

public List<List<Integer>> subsets (int[] nums) { List<List<Integer>> ans = new ArrayList<>(); backtrack(0,new ArrayList<>(),ans,nums); return ans; }

private void backtrack (int first, ArrayList<Integer> curList, List<List<Integer>> ans,int[] nums) {
ans.add(new ArrayList<Integer>(curList));
for (int i = first; i < nums.length;i++) {
curList.add(nums[i]);
backtrack(i+1,curList,ans,nums);
curList.remove(curList.size()-1); // 回溯，删掉用过的元素
}
}