题目:
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的
子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
思路:
- 回溯法
- 选择数组元素,如果数组元素全都选择完了,就添加到结果集里面
- 回溯移除最后添加的数组元素,移除后再次进行递归添加新的子集
代码:
class LeetCode78 {//存放结果集List<List<Integer>> resultList = new ArrayList<>();//存放已经被选中的数据List<Integer> list = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) {//回溯法 dfs (0, nums);return resultList;}public void dfs (int cur, int[] nums) {//如果全都选择完了,就添加到结果集里面if (cur == nums.length) {resultList.add(new ArrayList<Integer>(list));return;}//选择数组元素list.add( nums[cur]);//递归dfs(cur+1, nums);//回溯,移除刚添加的(也就是最后一个)元素,以便后面再重新选择list.remove( list.size()-1);// 移除后一个元素后,再次进行递归添加新的子集到list中dfs(cur+1, nums);}}