力扣78.子集
力扣78.子集
原题，题目描述：
题目会给我们一个数组（集合），我们需要找出这个集合的所有子集，包括空集。
思路一
题目的描述很短，但是这道题我真实的想了好久。然后我看了一下这道题的标签，是回溯，于是我写下了如下代码：
class Solution {
ArrayList<List<Integer>> subsetsRes = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
subsetsRes.add(new ArrayList<>());
int len = nums.length;
ArrayList<Integer> list = new ArrayList<>();
if (len==1){
list.add(nums[0]);
subsetsRes.add(list);
return subsetsRes;//subsetsRes.stream().toList();
}
for (int i : nums) {
list.add(i);
}
subsetsRes.add(list);
int[] t = new int[len - 1];
for (int i = 0; i < len; i++) {
System.arraycopy(nums, 0, t, 0, i);
System.arraycopy(nums, i+1, t, i, len-i-1);
subsets2(t);
}
return subsetsRes;//subsetsRes.stream().toList();
}
public void subsets2(int[] nums) {
int len = nums.length;
ArrayList<Integer> list = new ArrayList<>();
if (len==1){
list.add(nums[0]);
for (List<Integer> r : subsetsRes) {
if (r.equals(list)) {
return;
}
}
subsetsRes.add(list);
return;
}
for (int i : nums) {
list.add(i);
}
for (List<Integer> r : subsetsRes) {
if (r.equals(list)) {
return;
}
}
subsetsRes.add(list);
int[] t = new int[len - 1];
for (int i = 0; i < len; i++) {
System.arraycopy(nums, 0, t, 0, i);
System.arraycopy(nums, i+1, t, i, len-i-1);
subsets2(t);
}
}
}
顺序去掉数组中的元素传入下一递归，然后去掉重复的元素。毫无疑问，去重操作是非常耗时的，重复操作递归也非常耗时。所以这份答案的结果虽然通过，但是非常不理想。
我思考了很久，确实有点没想法了，就去看了官解，新学习了如下两种解法
解法二
我们可以逐步的添加元素至集合中，每次添加都和前面的元素融合，如下图：
了解解法后我们就可以写出如下代码：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
ArrayList<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>());
for (int num : nums) {
int size = res.size();
for (int i = 0; i < size; i++) {
ArrayList<Integer> newList = new ArrayList<>(res.get(i));
newList.add(num);
res.add(newList);
}
}
return res;
}
}
代码非常的简短，速度也是杠杠的，打败百分之百。
解法三
第三种解法是我觉得最有意思的：我们可以借助二进制数来构建子集，以集合{1,2,3}为力，我们选取一个 最低3位位1，其他位，除符号位为0的数字，做为for循环的终点数字。从0开始递增，我们，以上面的集合为例，这个数字为7，我们做for，会得到的数字序列为 0～7，二进制数为 000,001 010 011 ...... 110 111，我们使用数字的位置作为下标去数组里选取数字，如果对应的二进制位为0则不选，为1就将数字加入到数组。下面看代码：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
ArrayList<List<Integer>> res = new ArrayList<>();
int len = nums.length;
int target = 0;
for (int i = 0; i < len; i++) {
target = target << 1;
target = target | 1;
}
for (int i = 0; i <= target; i++) {
int temp = i;
ArrayList<Integer> list = new ArrayList<>();
for (int j = 0; j < len && temp != 0; j++) {
if((temp&1)==1){
list.add(nums[len-1-j]);
}
temp=temp>>>1;
}
res.add(list);
}
return res;
}
}
这个解法的速度也不错。
上面的解法时空复杂度都是 O(n\times 2n)，不过对于这种问题，这个是正常且必须的时空复杂度，因为展开后信息是爆炸性的。