leetcode_cpp/recall/46.cpp

/*
 * @Description:
 * @Version: 1.0
 * @Autor: zhuyijun
 * @Date: 2021-11-11 21:30:12
 * @LastEditTime: 2021-11-11 22:06:51
 */
//全排列   回溯问题
/*
给定一个不含重复数字的数组 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]]
 */
#include <bits/stdc++.h>
using namespace std;
//全部路径 路径全排列
vector<vector<int>> res;
/**
 * @brief
 *
 * @param nums  选择列表
 * @param list 路径记录在其中
 * 结束条件: nums中的元素全在list中
 */
void backtrack(vector<int>& nums, vector<int>& list) {
  // 结束条件
  if (list.size() == nums.size()) {
    res.push_back(list);
  }
  for (int num : nums) {
    //排除不合法的选择
    auto result = find(list.begin(), list.end(), num);
    if (result != list.end()) {
      continue;
    }
    //添做选择
    list.push_back(num);
    //进入下一层决策树
    backtrack(nums, list);
    result = remove(list.begin(), list.end(), num);
    //取消选择
    list.erase(result);
  }
}
vector<vector<int>> permute(vector<int>& nums) {
  vector<int> list;
  backtrack(nums, list);
  return res;
}

//测试

int main() {
  vector<int> nums;
  nums.push_back(1);
  nums.push_back(2);
  nums.push_back(3);
  auto res = permute(nums);
  for (auto result : res) {
    for (auto r : result) {
      cout << r << " ";
    }
    cout << endl;
  }
  return 0;
}