C++简洁版全排列代码
《代码随想录》在回溯章节中的全排列代码模板较为复杂，其实还有一种常用写法，思路是交换元素位置后做dfs(),并回溯。对应leetcode46题。
class Solution {
public:vector<vector<int>> res;void dfs(vector<int>num, int k){// k代表换到哪个下标了：如果为size，则表明都换过了if (k == num.size()){vector<int> path;for (int i = 0; i < k; i++)path.push_back(num[i]);res.push_back(path);return;}for (int i = k; i < num.size(); i++){{int t = num[i]; num[i] = num[k]; num[k] = t; }dfs(num, k + 1);{int t = num[i]; num[i] = num[k]; num[k] = t; }}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums, 0);return res;}
};简单对比全排列和组合的dfs模板的区别：
两者均使用dfs和回溯的思想
- 全排列和组合的主要区别是全排列的回溯部分是交换，组合的回溯部分是对路径做push()和pop()。
- 组合的数量需要有参数或变量限制选取个数，而全排列一定到达末尾，参数使用较少。