子集Leetcode


难度级别 中等
经常问 亚马逊 Apple 彭博 ByteDance Facebook 谷歌 微软 神谕
排列 回溯 位操作

在子集Leetcode问题中,我们给出了一组不同的整数nums,打印所有子集(幂集)。

请注意: 解决方案集不得包含重复的子集。

如果可以通过删除某些(可能为零或全部)元素从B获得a,则数组A是数组B的子集。

使用案列

输入:

[1,2,3]

输出:

[1],[2],[1、2],[3],[1、3],[2、3],[1、2、3]

方法1:使用位操作的迭代解决方案

一组n个元素的每个子集可以表示为n个位的序列,它对应于0…2n-1之间的整数。 位序列中的那些指示子集中包含哪些元素。

算法

  1. 声明 排列 向量“ ans”,我们将在其中存储所有子集。
  2. 初始化代表nums_array大小的变量n。
  3. 在0到2的范围内为我运行一个循环n-1
    1. 初始化数组“ temp”,将在其中存储当前子集。
    2. 对j进行循环,范围为0到n-1
      1. 如果I的第j位被设置,则将nums [i]添加到临时数组。
    3. 将“临时”数组添加到“ ans”
  4. 打印最终的ans数组。

打印所有子集的实现

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    for (int i = 0; i < (1 << (nums.size())); i++)
    {
        vector<int> temp;
        for (int j = 0; j < nums.size(); j++)
        {
            if (i & (1 << j))
            {
                temp.push_back(nums[j]);
            }
        }
        ans.push_back(temp);
    }
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

打印所有子集的复杂度分析

时间复杂度

我们运行两个嵌套循环,一个范围为2 ^ n,另一个范围为n。 因此最终时间复杂度为O(2 ^ n * n)。

空间复杂度

有2 ^ n-1个子集,每个子​​集平均需要O(n)个空间,因此总空间复杂度为O(2 ^ n * n)。

我们可以优化它吗?

是的,我们可以使用回溯来优化它,让我们看看如何!

方法2:使用回溯的递归解决方案

我们遍历nums数组,对于每个位置,我们有两个选择,要么选择ith元素,要么跳过它。

算法

  1. 创建一个函数,该函数接受参数,最终答案数组,当前子集数组,输入数组以及指向nums数组中当前元素的变量“ index”。
  2. 基本条件:如果“索引”等于nums数组的大小,则将当前子集数组添加到最终答案中,因为现在我们无法再遍历nums数组。
  3. 我们现在有两个选择
    1. 跳过当前元素,并使用index + 1调用递归函数,所有其他参数将保持不变。
    2. 将当前元素添加到当前子集中,并使用索引+1和其他参数调用递归函数。 调用递归函数后,通过从当前子集中删除最后一个元素来执行回溯步骤。
  4. 打印最终答案。

举例说明

让我们以一个输入数组nums = [1,2,3]

然后,递归树将如下所示:

子集Leetcode

在上面的树中,Subset(i)是递归函数,其中i表示当前索引。

打印所有子集的实现

子集Leetcode的C ++程序

#include <bits/stdc++.h>
using namespace std;
void subsets(vector<vector<int>> &ans, vector<int> &temp, vector<int> &nums, int i)
{
    if (i == nums.size())
    {
        ans.push_back(temp);
        return;
    }
    subsets(ans, temp, nums, i + 1);
    temp.push_back(nums[i]);
    subsets(ans, temp, nums, i + 1);
    temp.pop_back();
    return;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    vector<int> temp;
    subsets(ans, temp, nums, 0);
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

子集Leetcode的JAVA程序

import java.util.*; 
public class Main
{
    static List<List<Integer>> res;
    public static void subsets(int[] nums,int index,List<Integer> list){
        if(index==nums.length-1){
            res.add(new ArrayList<Integer>(list));
            list.add(nums[index]);
            res.add(new ArrayList<Integer>(list));
            list.remove(list.size()-1);
            return;
        }
        subsets(nums,index+1,list);
        list.add(nums[index]);
        subsets(nums,index+1,list);
        list.remove(list.size()-1);
    }
  public static void main(String[] args) {
      res = new ArrayList<>();
      int[] nums={2, 3, 4};
      List<Integer> list = new ArrayList<Integer>();
      subsets(nums, 0, list);
      for(List<Integer> subset:res){
          for(int i: subset){
              System.out.print(i+", ");
          }
            System.out.println();
      }
  }
}

4, 
3, 
3, 4, 
2, 
2, 4, 
2, 3, 
2, 3, 4, 

子集Leetcode的复杂度分析

时间复杂度

对于每个索引,我们进行2次递归调用,并且有n个元素,因此总时间复杂度为O(2 ^ n)。

空间复杂度

有2 ^ n-1个子集,每个子​​集平均需要O(n)个空间,因此总空间复杂度为O(2 ^ n * n)。

參考資料