LeetCode题目之腾讯精选练习（50题）：子集

野性酷女 2024-04-18 18:42 119阅读 0赞

# 题目 #

给定一组**不含重复元素**的整数数组 nums，返回该数组所有可能的子集（幂集）。

**说明**：解集不能包含重复的子集。

**示例** :

输入: nums = [1,2,3]
    输出:
    [
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    ]

## 算法实现 ##

public IList<IList<int>> Subsets(int[] nums)
    {
        
        IList<IList<int>> list = new List<IList<int>>();
        list.Add(new List<int>());
        int len;
        for (int i = 0; i < nums.Length; i++)
        {
        
            len = list.Count;//记录要复制的元素数
            for (int j = 0; j < len; j++)//复制子集
            {
        
                list.Add(new List<int>(list[j]));
            }
            for (int k = len; k < list.Count; k++)//对后面复制的子集加入当前元素
            {
        
                list[k].Add(nums[i]);
            }
        }
        return list;
    }

## 执行结果 ##

**执行结果** : 通过  
**执行用时** : 368 ms, 在所有 C\# 提交中击败了72.22%的用户  
**内存消耗** : 29.6 MB, 在所有 C\# 提交中击败了6.67%的用户  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]

## 小的总结 ##

这道题对我来说有些困难，打算先找到规律，但是失败了，后来看了解题，知道了一种算是递归的方法，能够理解，并自己编了程序。后面的回溯法移植到c\#上虽然成功，但稍有些不懂。

## 回溯法 ##

//回溯法
    private IList<IList<int>> res;
    private void find(int[] nums, int begin, IList<int> pre)
    {
        
        // 没有显式的递归终止
        res.Add(new List<int>(pre));// 注意：这里要 new 一下
        for (int i = begin; i < nums.Length; i++)
        {
        
            pre.Add(nums[i]);
            find(nums, i + 1, pre);
            pre.RemoveAt(pre.Count - 1);// 组合问题，状态在递归完成后要重置
        }
    }
    public IList<IList<int>> Subsets(int[] nums)
    {
        
        int len = nums.Length;
        res = new List<IList<int>>();
        if (len == 0)
        {
        
            return res;
        }
        IList<int> pre = new List<int>();
        find(nums, 0, pre);
        return res;
    }

![在这里插入图片描述][20190910173933241.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU2NTk5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7d1f04e88b134a469a4a148b488031b8.png
[20190910173933241.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7af8f40dc43c407bbc9e974eda926be4.png