一、题目
1、算法题目
“给定整数数组，数组中元素不相同，返回所有可能的子集，子集不重复。”
题目链接：
来源：力扣（LeetCode）
链接：78. 子集 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1： 输入： nums = [1,2,3] 输出： [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 复制代码
示例 2： 输入： nums = [0] 输出： [[],[0]] 复制代码
二、解题
1、思路分析
这道题跟77题很相似，77题是求所有的组合，也就是解决问题的所以方法，用到了回溯算法。
而这道题与77题不同的地方在于，这个求出的所有组合不能包含重复的元素。
这类题都可以使用回溯算法，回溯算法的关键在于不合适就返回上一步，或者进行递归调用，进入下一层。
然后通过题意，找到约束条件，减少时间复杂度。
2、代码实现
代码参考：
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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n x 2n)
一共有2n个状态，每个状态需要O(n)的时间来构造，所以是 O(n x 2n)
空间复杂度： O(n)
只需要使用一个临时数组n的空间即可。
三、总结
回溯算法是深度优先遍历算法，对于子集问题，排列问题而言，不计较一个组合内元素的顺序性。
因此需要按某种顺序展开搜索，才能不遗漏。
然后根据条件判处重复项，最后得到的就是我们要的答案。
