字符串的組合算法問題的C語言實(shí)現(xiàn)攻略

1、字符串的組合算法問題的C語言實(shí)現(xiàn)攻略關(guān)于字符串的組合算法問題的C語言實(shí)現(xiàn)攻略關(guān)于字符串的組合算法問題的C語言實(shí)現(xiàn)攻略題目：輸入一個(gè)字符串，輸出該字符串中字符的所有組合。舉個(gè)例子，如果輸入abc，它的組合有a、b、c、ab、ac、bc、abc。上面我們?cè)敿?xì)討論了如何用遞歸的思路求字符串的排列。同樣，本題也可以用遞歸的思路來求字符串的組合。假設(shè)我們想在長(zhǎng)度為n的字符串中求m個(gè)字符的組合。我們先從頭掃描字符串的第一個(gè)字符。針對(duì)第一個(gè)字符，我們有兩種選擇：第一是把這個(gè)字符放到組合中去，接下來我們需要在剩下的n-1個(gè)字符中選取m-1個(gè)字符；第二是不把這個(gè)字符放到組合中去，接下來我們需要在剩下的n-1個(gè)字

2、符中選擇m個(gè)字符。這兩種選擇都很容易用遞歸實(shí)現(xiàn)。下面是這種思路的參考代碼：#include#include#includeusing namespace std;#includevoid Combination(char *string ,int number,vector&result);void Combination(char *string) assert(string != NULL); vectorresult; int i , length = strlen(string); for(i = 1 ; i = length ; +i) Combination(string , i

3、,result);void Combination(char *string ,int number , vector&result) assert(string != NULL); if(number = 0) static int num = 1; printf(第%d個(gè)組合t,num+); vector:iterator iter = result.begin(); for( ; iter != result.end() ; +iter) printf(%c,*iter); printf(n); return ; if(*string = ) return ; result.push_b

4、ack(*string); Combination(string + 1 , number - 1 , result); result.pop_back(); Combination(string + 1 , number , result);int main(void) char str = abc; Combination(str); return 0;由于組合可以是1個(gè)字符的組合，2個(gè)字符的字符一直到n個(gè)字符的組合，因此在函數(shù)void Combination(char* string)，我們需要一個(gè)for循環(huán)。另外，我們用一個(gè)vector來存放選擇放進(jìn)組合里的字符。用位運(yùn)算來實(shí)現(xiàn)求組合#

5、includeusing namespace std;int a = 1,3,5,4,6;char str = abcde;void print_subset(int n , int s) printf(); for(int i = 0 ; i n ; +i) if( s&(1i) ) / 判斷s的二進(jìn)制中哪些位為1，即代表取某一位 printf(%c ,stri); /或者ai printf(n);void subset(int n) for(int i= 0 ; i (1n) ; +i) print_subset(n,i); int main(void) subset(5); return

6、 0;全組合例如給定字符串“abc”，全組合意思從中去0個(gè)元素，1個(gè)元素，一直到n個(gè)元素，介紹二進(jìn)制做法。以字符串“abc”為例：000 NULL001 c010 b011 bc100 a101 ac110 ab111 abc思路出來了，代碼也比較好寫，分享一下我的代碼：/* * Write a method that returns all subsets of a set */ #include#include#include/* * 通過0到2-1來標(biāo)識(shí)子集 * * T = (n * 2n) * */ void getSubset(char *str, int len) int i, m

7、ax, index, j; max = 1 len; for (i = 1; i = 1; index +; printf(n); int main(void) char str1000; while (scanf(%s, str) != EOF) getSubset(str, strlen(str); return 0; 從n中選m個(gè)數(shù)這里分為兩種方法：遞歸和回溯遞歸遞歸思路如下，從n個(gè)數(shù)中取出m個(gè)數(shù)，可以分解為以下兩步：從n個(gè)數(shù)中選取編號(hào)最大的數(shù)，然后在剩下的n-1個(gè)數(shù)中選取m-1個(gè)數(shù)。直到從n-(m-1)中選取一個(gè)數(shù)為止 從n個(gè)數(shù)中選取次小的數(shù)，重復(fù)1的操作代碼如下：/* * 遞歸法解決

8、組合問題 */ void combine(int *arr, int n, int m, int *tmp, const int M) int i, j; for (i = n; i = m; i -) tmpm = i; if (m = 0) / 選出m個(gè)數(shù) for (j = 0; j M; j +) printf(%d , arrtmpj); printf(n); else combine(arr, i - 1, m - 1, tmp, M); DFS其實(shí)考慮到用dfs，這道題目就簡(jiǎn)單很多，dfs的回溯條件就是臨時(shí)數(shù)組的大小=k即可，同時(shí)附加一道LeetCode上的題目，用dfs思路ac題

9、目Given two integers n and k, return all possible combinations of k numbers out of 1 . n.For example,If n = 4 and k = 2, a solution is:ac代碼public class Solution public static ArrayListcombine(int n, int k) ArrayListrs = new ArrayList(); ArrayListlist = new ArrayList(); dfs(1, k, n, list, rs); return rs; public static void dfs(int pos, int k, int n, ArrayListlist, ArrayListrs) if (li