1.27回溯（中等）

1.全排列 + 全排列 II

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

2.给定一个可包含重复数字的序列 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]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10

分析：是回溯的全排列类型，刚开始写的时候传参传的不是used的地址，所以used里面持续是0

#include <bits/stdc++.h>
using namespace std;
vector<int> nums;
vector<int> path;
vector<bool> used(nums.size(),false);
void f(vector<int> nums,vector<bool> &used)
{if(nums.size()==path.size()){for(int i=0;i<path.size();i++) cout<<path[i]<<" ";cout<<endl;return;}for(int i=0;i<nums.size();i++){if(used[i] == true) continue;used[i]=true;path.push_back(nums[i]);f(nums,used);path.pop_back();used[i]=false;}
}
main()
{int x;while(cin>>x){nums.push_back(x);}f(nums,used);
}

 分析：这个剪枝不是很好理解，if(nums[i]==nums[i-1] && used[i-1] == false) continue;这里是对同一层进行剪枝，同一层表示的是同一个位置，如果这个位置上的数重复了，那我们就直接continue

#include <bits/stdc++.h>
using namespace std;
vector<int> nums;
vector<int> path;
vector<bool> used(nums.size(),false);
void f(vector<int> nums,vector<bool> &used)
{if(nums.size()==path.size()){for(int i=0; i<path.size(); i++) cout<<path[i]<<" ";cout<<endl;return;}for(int i=0; i<nums.size(); i++){if(nums[i]==nums[i-1] && used[i-1] == false) continue;if(used[i]==false){used[i]=true;path.push_back(nums[i]);f(nums,used);path.pop_back();used[i]=false;}}
}
main()
{int x;while(cin>>x){nums.push_back(x);}sort(nums.begin(),nums.end());f(nums,used);
}

2.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

分析： 这个在我看来属于回溯的组合型，我打算用组合型来做

#include <bits/stdc++.h>
using namespace std;
vector<int> path;
int num[21];
int n,k;
void f(int n)
{int i,j;int d=k-path.size();if(path.size()==k){for(i=0;i<k;i++)cout<<path[i]<<" ";cout<<endl;return;}for(j=n;j>d-1;j--){path.push_back(j);f(j-1);path.pop_back();}
}
main()
{cin>>n>>k;f(n);
}

3.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

分析：这个用选和不选的类型来做思路就比较清晰了

#include <bits/stdc++.h>
using namespace std;
vector<int> path;
int num[21],n;
void f(int i,int index)
{if(i==n){for(int j=0; j<index; j++) cout<<path[j]<<" ";cout<<endl;return;}f(i+1,index);path.push_back(num[i]);f(i+1,index+1);path.pop_back();
}
main()
{int x,i=0;while(cin>>x){num[i]=x;i++;}n=i;f(0,0);
}