一、問題背景

??突發(fā)奇想就是想利用遞歸方法來求解數(shù)字的排列組合的問題，感覺數(shù)字排列組合使用遞歸求解起來是比較方便簡潔的，我們只需要定義好終止條件以及我們需要剪枝的一些條件。

問題1：給出一個正數(shù)n，我們需要求解出0到n-1范圍內(nèi)多個數(shù)字能組合成多少個數(shù)。例如，n=3，則可以組成：102、120、210、201四種數(shù)字組合。
其實(shí)通過我們的分析，由于0不能作為數(shù)字的首位，其余數(shù)字可以位于任何的位置，則最后的排列情況有 n*n! 次。

下面我們通過遞歸的方式來復(fù)雜化求解過程 雖然把問題從簡單到復(fù)雜，但這也是有助于我們理解遞歸的過程，可以推導(dǎo)到更加復(fù)雜的排列組合情況。

全排列問題 — 解決方案：

#include <iostream> #include <vector> #include <string> using namespace std;#include <iostream> #include <vector> #include <string> using namespace std;void _combine(int &res, string str, int start, int n, vector<bool> &used) {if (str.length()==n && str[0]!='0') {cout<<str<<endl;res += 1;return;}for (int i=0; i<n; i++) {if (!used[i]) {//if(i>0&&nums[i]==nums[i-1]&&!used[i-1])// 這一段代碼是用來對所給的排列數(shù)字或字母存在重復(fù)的進(jìn)行判重剪枝去掉重復(fù)的排列方式。（條件：將開始的序列排序使得相同的字母數(shù)字相鄰）// continue;used[i] = true;_combine(res, str+to_string(i), start+1, n,used);used[i] = false;}} } int findNumbers(int n) {if (n==0) return 0;if (n<=2) return 1;int res=0;vector<bool> used(n, false);_combine(res,"",0,n, used);return res; } int main() {int res = 0;res = findNumbers(4);cout << "nums ="<<res<<endl;return 0; }

這種全排列問題我們采用的是回溯的方法來求解，自然而然就讓我想到了經(jīng)典的回溯問題，八皇后的排列問題，跟這個題本質(zhì)上是一致的，這里我們可以回顧一下：

題目[leetcode 51]
n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。
攻擊的范圍是上下左右和四個斜方向在棋盤中的所有位置。

求解方法如下：

#include <bits/stdc++.h> using namespace std;void putQueue(int k, int j, vector<vector<int>> &mark) {vector<int> x = {0,0,1,-1,1,-1,1,-1};vector<int> y = {1,-1,0,0,1,1,-1,-1};for (int i=1; i<mark.size(); i++) {for (int k=0; k<8; k++) {int new_x = k+i*x[k];int new_y = j+i*y[k];if (new_x >=0&&new_x<mark.size()&&new_y >=0&&new_y<mark.size()) {mark[new_x][new_y] = 1;}}}}void generate(int k, int n, vector<string> &loc, vector<vector<string>> &res, vector<vector<int>> &mark) {if (k==n) {res.push_back(loc);return;}for (int i=0; i<n; i++) {if(mark[k][i]==0) {vector<vector<int>> mark_pre = mark;loc[k][i] = 'Q';putQueue(k, j, mark);generate(k+1, n, loc, res, mark);mark = mark_pre;loc[k][i] = '.';}} }// 這里我們推廣到N皇后的問題 vector<vector<string>> solveNQueens(int n) {vector<vector<string>> result; // 保存最終的所有滿足情況的結(jié)果vector<vector<int>> mark(n, vector<int> (n, 0)); // 標(biāo)記棋盤上還能放置皇后的位置vector<string> location; // 保存棋盤上皇后的位置for(int i = 0; i < n; i++){ location.push_back("");//棋盤的構(gòu)造location[i].append(n, '.');}generate(0, n, location, result, mark); //dfs函數(shù)調(diào)用return result; }

問題2：給定兩個整數(shù)n和k，從n中返回k個數(shù)字的所有可能組合。例如，n=4和k=2的情況下，返回的組合即如果為：
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]

子集 — 解決方案：

#include <iostream> #include <vector> #include <string> using namespace std;void _combine(vector<vector<int>> &res, vector<int> &tmp, int n, int k, int start) {if (tmp.size()==k) {res.push_back(tmp);return;}for (int i=start; i<=n; i++) {tmp.push_back(i);_combine(res, tmp, n, k, i+1);tmp.pop_back();} } vector<vector<int>> combineNums(int n, int k) {vector<vector<int>> res;vector<int> tmp;if (k>n || k==0) return res;_combine(res, tmp, n, k, 1);return res; } int main() {vector<vector<int>> res;res = combineNums(4, 2);for (int i=0; i<res.size(); i++) {for (int j=0; j<res[0].size(); j++) {cout <<res[i][j]<<" ";}cout<<endl;}return 0; }

綜上所述，有篇文章總結(jié)的比較經(jīng)典：C++ 總結(jié)了回溯問題類型 帶你搞懂回溯算法(排列篇)
首先我們明白一點(diǎn)，全排列問題和 子集、組合這是兩類問題，我們應(yīng)該分別對待，總結(jié)來說呢就是文章所提的：

“排列”類型問題和“子集、組合”問題不同在于：“排列”問題使用used數(shù)組來標(biāo)識選擇列表，而“子集、組合”問題則使用start參數(shù)。另外還需注意兩種問題的判重剪枝！！

總結(jié)

以上是生活随笔為你收集整理的【C++】数字的组合排列情况的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。