“给定整数数组,数组中元素不相同,返回所有可能的子集,子集不重复。”
题目链接:
来源:力扣(LeetCode)
链接:78. 子集 - 力扣(LeetCode) (leetcode-cn.com)
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入: nums = [1,2,3]
输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入: nums = [0]
输出: [[],[0]]
这道题跟77题很相似,77题是求所有的组合,也就是解决问题的所以方法,用到了回溯算法。
而这道题与77题不同的地方在于,这个求出的所有组合不能包含重复的元素。
这类题都可以使用回溯算法,回溯算法的关键在于不合适就返回上一步,或者进行递归调用,进入下一层。
然后通过题意,找到约束条件,减少时间复杂度。
代码参考:
class Solution {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
t.add(nums[i]);
}
}
ans.add(new ArrayList<Integer>(t));
}
return ans;
}
}
时间复杂度 : O(n x 2n)
一共有2n个状态,每个状态需要O(n)的时间来构造,所以是 O(n x 2n)
空间复杂度: O(n)
只需要使用一个临时数组n的空间即可。
回溯算法是深度优先遍历算法,对于子集问题,排列问题而言,不计较一个组合内元素的顺序性。
因此需要按某种顺序展开搜索,才能不遗漏。
然后根据条件判处重复项,最后得到的就是我们要的答案。