LeetCode_回溯_中等_78.子集

目录

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

示例 1：

输入：nums = [1,2,3]

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

提示：

1 <= nums.length <= 10

-10 <= nums[i] <= 10

nums 中的所有元素 互不相同

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/subsets

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.思路

（1）回溯

经过分析可知，本题可以看作是在LeetCode77.组合这题的基础上，针对组合中的整数个数 k 进行一次0~nums.length的循环，因为本题中子集元素的个数就相当于那题一个组合中元素的个数，所以只需将那题中的回溯代码稍加修改即可。

3.代码实现（Java）

//（1）回溯
class Solution {

    List<List<Integer>> res = new ArrayList<List<Integer>>();
    LinkedList<Integer> path = new  LinkedList<Integer>();

    public List<List<Integer>> subsets(int[] nums) {
        int length = nums.length;
        for(int i=0;i<=length;i++){
            backTrack(0,length,i,nums);
        }
        //res.add(Arrays.asList(nums));
        return res;
    }

    public void backTrack(int index, int length, int k,int[] nums){
        //存放符合条件的结果
        if(path.size()==k){
            res.add(new ArrayList<Integer>(path));
            return;
        }
        /*
            循环限制条件i<=n-(k-path.size())+1的目的是剪枝优化
            i:当前选择的整数在[1,n]中的位置，同时也是被选择的整数本身
            path.size():已经选择的整数个数
            k-path.size():待选择的元素个数
            n-(k-path.size())+1:在nums[0...length-1]中至少要开始遍历的位置(包括起始位置，所以要+1)，否则将不能得到k个数的组合
        */
        for(int i=index;i<length-(k-path.size())+1;i++){
            //将当前节点加入到path中
            path.add(nums[i]);
            //下一层搜索从i+1开始
            backTrack(i+1,length,k,nums);
            //删除并返回最后一个元素
            path.removeLast();
        }
    }
}