在力扣上刷到的這類題，做一個總結，以下例子均來源于力扣。思路相似，都可以用回溯（決策樹）解決。
這類題型的原理可參考這兩篇題解，講得非常詳細！
1、扒一扒回溯算法的褲子
2、回溯思想團滅排列、組合、子集問題
? ? ? ?

? ? ? ?

下面是C++實現的代碼

? ? ? ?

? ? ? ?

排列

全排列 ：給定一個 沒有重復 數字的序列，返回其所有可能的全排列。
示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

或者給定一個可包含重復數字的序列，返回所有排列，重復的排列也要返回。
示例:
輸入: [1,1,2]
輸出:
[
[1,1,2],
[1,2,1],
[1,1,2],
[1,2,1],
[2,1,1]
[2,1,1]
]

class Solution { public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;vector<int> track;vector<int> visited(nums.size(),0);back_track(nums,track,res,visited);return res;}void back_track(vector<int> &nums,vector<int> &track,vector<vector<int>> &res,vector<int> &visited){int siz=nums.size();if(track.size()==siz){res.push_back(track);return;}for(int i=0;i<siz;++i){ if(visited[i]==1){continue;}visited[i]=1;track.push_back(nums[i]);back_track(nums,track,res,visited);track.pop_back(); visited[i]=0; }return;} };

? ? ? ?

? ? ? ?

全排列II：給定一個可包含重復數字的序列，返回所有不重復的全排列。
示例:
輸入: [1,1,2]
輸出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutations-ii

class Solution { public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;vector<int> track;vector<int> visited(nums.size(),0);sort(nums.begin(),nums.end());back_track(nums,res,track,visited);return res;}void back_track(vector<int>& nums,vector<vector<int>> &res,vector<int> &track,vector<int> &visited){int siz=nums.size();if(track.size()==siz){res.push_back(track);return;}for(int i=0;i<siz;++i){ if(visited[i]==1 || (i>0 && visited[i-1]==0 && nums[i]==nums[i-1])){continue;}visited[i]=1;track.push_back(nums[i]);back_track(nums,res,track,visited);track.pop_back();visited[i]=0;}return;} };

? ? ? ?

? ? ? ?

組合

給定兩個整數 n 和 k，返回 1 … n 中所有可能的 k 個數的組合。

示例:

輸入: n = 4, k = 2
輸出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/combinations

class Solution { public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> res;vector<int> track; // 路徑：在決策樹中已經做出的選擇back_track(n,k,1,track,res); return res;}void back_track(int n,int k,int start,vector<int> &track,vector<vector<int>> &res){if(track.size()==k){ // 遞歸結束條件：路徑大小==k，到達決策樹底層res.push_back(track);return;}for(int i=start;i<=n;++i){ // i 從 start 開始遞增track.push_back(i);back_track(n,k,i+1,track,res);track.pop_back();}} };

? ? ? ?

? ? ? ?

子集

給定一組不含重復元素的整數數組 nums，返回該數組所有可能的子集。
示例:
輸入: nums = [1,2,3]
輸出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subsets

方法一，回溯法：

class Solution { public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> res;vector<int> track;back_track(nums,0,track,res);return res;}void back_track(vector<int>& nums,int start,vector<int>& track,vector<vector<int>>& res){res.push_back(track);int siz=nums.size();for(int i=start;i<siz;++i){track.push_back(nums[i]);back_track(nums,i+1,track,res);track.pop_back();}} };

? ? ? ?

方法二，遞歸：
// 空集的子集：{}
// 有一個元素的集合{a}的子集：{}、{a}
// 有兩個元素的集合{a,b}的子集：{}、{a} 、{b}、{a,b}
// 集合每增加一個元素，其子集為：原集合子集、原集合的每個子集中加上新增加的這個元素

vector<vector<int>> subsets(vector<int>& nums) {// 遞歸結束條件：nums為空，返回一個空集。if (nums.empty()) return { {} };int n = nums.back(); // 把nums最后一個元素拿出來nums.pop_back();vector<vector<int>> res = subsets(nums); // 前面元素的所有子集// 然后在 前面元素的所有子集 后增加這個元素int siz = res.size();for (int i = 0; i < siz; i++) {res.push_back(res[i]);res.back().push_back(n);}return res; }

子集II：給定一個可能包含重復元素的整數數組 nums，返回該數組所有可能的子集，解集不能包含重復的子集。
示例:
輸入: [1,2,2]
輸出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/subsets-ii

class Solution { public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<vector<int>> res;vector<int> track;sort(nums.begin(),nums.end());back_track(nums,0,track,res);return res;}void back_track(vector<int>& nums,int start,vector<int> &track,vector<vector<int>> &res){ res.push_back(track); int siz=nums.size();for(int i=start;i<siz;++i){if(i>start && nums[i]==nums[i-1]){continue;}track.push_back(nums[i]);back_track(nums,i+1,track,res);track.pop_back();}} };

總結

以上是生活随笔為你收集整理的【C++代码】求全排列、组合、子集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。