1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677 |
- /*
- * @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;
- }
|