力扣(LeetCode)78

题目地址：

https://leetcode-cn.com/probl...

题目描述：

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

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

示例:

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

输出:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

解答：

这一题用回溯法。对于长度为n的nums数组，它的解空间应该是这样的[x1,x2,x3...,xn]

这里的xn=0或者1，代表第n个数放或者不放入子集。

java ac代码：

class Solution {
    List<List<Integer>>ans = new ArrayList(1000);
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(0,nums.length,new boolean[nums.length],nums);
        return ans;
    }
    void backtrack(int i,int n,boolean[]flag,int[]nums)
    {
        if(i == n)
        {
            List<Integer> temp = new ArrayList(n);
            for(int j = 0;j < flag.length;j++)
                if(flag[j])temp.add(nums[j]);
            ans.add(temp);
            return;
        }
        backtrack(i+1,n,flag,nums);
        flag[i] = true;
        backtrack(i+1,n,flag,nums);
        flag[i] = false;
        
    }
}