leetcode

46.全排列

力扣链接

class Solution {
public:
    // 初始化一定不能放到 回溯函数中 或者递归函数中 否则每次回溯会重置变量
    std::vector<std::vector<int>> res;
    std::vector<int> path;
  
    void backtracking(std::vector<int> nums, std::vector<int>& used){// 也可std::vector<int> used 不引用
      if (nums.size() == path.size()){
        res.push_back(path);
        return;
      }
      for (int i = 0; i < nums.size(); i++){
        if (used[i]) continue;
        // 走过标记为 1
        used[i] = 1;
        path.push_back(nums[i]);
        backtracking(nums, used);
        used[i] = 0;
        path.pop_back();
      }
    }  

    std::vector<vector<int>> permute(std::vector<int>& nums) {
      // 或 std::vector<bool> 必须要初始化长度,否则直接索引有指针问题
      std::vector<int> used(nums.size());
      backtracking(nums, used);
      return res;
    }
};