共计 664 个字符,预计需要花费 2 分钟才能阅读完成。
题目地址: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;
}
}