【递归】 LeetCode46. 全排列

骑猪看日落 2022-12-03 05:21 157阅读 0赞

### 题目 ###

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

### 解答 ###

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

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

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

放小球问题，有三个盒子，将每个数放入某个盒子里。  
树的层为三个盒子，树的深度为这个盒子放入哪个数。

![在这里插入图片描述][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>
    
    // 46. Permutations
    
    // 递归完，相当于一个棵树的遍历，j是递归的层次，j=1则进入树的第一层，深度遍历，j+1，进入树的第二层。
    void Permute(std::vector<std::vector<int>>& results, std::vector<int>& nums, std::size_t j) { 
      // 当j等于0时，for循环是给第一个位置放N种可能的球。
      if (j < nums.size()) { 
        for (std::size_t i = j; i < nums.size(); ++i) { 
          std::swap(nums[j], nums[i]);
          // j+1是给下一个位置放球。
          Permute(results, nums, j + 1);
          std::swap(nums[j], nums[i]);
        }
      } else { 
        results.push_back(nums);
      }
    }
    
    std::vector<std::vector<int>> permute(std::vector<int>& nums) { 
      std::vector<std::vector<int>> results;
      Permute(results, nums, 0);
      return results;
    }
    
    int main() { 
      std::vector<int> nums{  1, 2, 3 };
      std::vector<std::vector<int>> results = permute(nums);
    
      for (const auto& result : results ) { 
        for (auto num : result) { 
          std::cout << num << " ";
        }
        std::cout << std::endl;
      }
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b82d9c87120842298550ec69367342dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/031b29a38254475a901c0bb61517deb6.png