【递归】 LeetCode78. 子集

川长思鸟来 2022-12-03 05:21 193阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]![在这里插入图片描述][20200901212629947.png_pic_center]

### 解答 ###

> 回溯法的求解过程实质上是一个先序遍历一棵状态树的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历的过程中。

> 递归题的解法：首先把题目的决策树画出来，树的层就是for循环，树的深度就是要递归的参数i。画出决策树后，找规律，进行剪枝。

**E.g.** 输入【1, 2, 3】

树的层为是否存在该数，树的深度为第N个数。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]

### 代码 ###

#include <iostream>
    #include <string>
    #include <list>
    #include <vector>
    #include <map>
    #include <utility>
    #include <functional>
    #include <algorithm>
    #include <cassert>
    
    // 78. Subsets
    
    // i是递归层次，i=1时，该位置的数存在，深度遍历，先判断i+1层。
    void Func(std::size_t i, const std::vector<int>& nums, std::vector<std::vector<int>>& subsets, std::vector<int>& subset) { 
      if (i >= nums.size()) { 
        subsets.push_back(subset);
        return;
      }
    
      // 位置i的数存在。
      subset.push_back(nums[i]);
      Func(i + 1, nums, subsets, subset);
      subset.pop_back();
    
      // 位置i的数不存在。
      Func(i + 1, nums, subsets, subset);
    }
    
    std::vector<std::vector<int>> GetSubsets(const std::vector<int>& nums) { 
      std::vector<std::vector<int>> subsets;
      std::vector<int> subset;
    
      Func(0, nums, subsets, subset);
    
      return subsets;
    }
    
    void PrintSubsets(const std::vector<std::vector<int>>& subsets) { 
      for (const std::vector<int>& subset : subsets) { 
        for (const int num : subset) { 
          std::cout << num << " ";
        }
        std::cout << std::endl;
      }
    }
    
    int main() { 
      PrintSubsets(GetSubsets({  1, 2, 3 }));
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200901212617418.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU=,size_16,color_FFFFFF,t_70#pic_center
[20200901212629947.png_pic_center]: /images/20221123/c13ef8ebc34942e0b3e3f965716ccce5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/bdb0cdfe3a394ff4ad211d7c07336ba3.png