全排列

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3] , [1,3,2] , [2,1,3] , [2,3,1] , [3,1,2] , [3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1] , [1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]

这个题目和上一个题目很像，但是要注意的是，这个题目是全排列，而上一个题目是组合，所以这个题目要注意的是，每次都要从0开始枚举，而不是从i开始枚举。而且需要一个数组来记录是否已经被选过了。

class Solution {
public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> temp;
    int n=nums.size();
    vector<int> visited(n,0);       
    //i代表正常处理的第几位
    function<void(int)> dfs =[&](int i){
      //递归出口
      if(i==n){
        res.emplace_back(temp);
        return;
      }
      //枚举选哪个
      for(int j=0;j<n;++j){
        if( !visited[j] ){//没被访问过
          temp.push_back(nums[j]);
          visited[j] =1;
          dfs(i+1);
          visited[j] =0;
          temp.pop_back();
        }
      }
    };
    dfs(0);
    return  res;
  }
};

更新日志

2024/12/15 12:44

查看所有更新日志

• 64700-update leetcode于 2024/12/15