本文共 7270 字，大约阅读时间需要 24 分钟。

word search、subsets I / II、N-Queens I / II、Permutations I / II

回溯算法，backtracking，就是穷举所有可能的结果，记录已经走过的路（如用vector等写入1），当此路走不通时，就擦除这一步的影响（写入0），回溯到上一步，重新选择。可以将所有的结果，写成树的形式。

for循环中的递归很难理解，看到网友说：递归是将大问题不断变成小问题，for循环是先把大问题变成很多子问题。

1.Word Search

flag数组用来标记，找到了要找的字符，标记为1；当后面的结果说明这一点不可取时再写成0.

bool findNext(char** board, int boardRowSize, int boardColSize, int i, int j, char* word, int n, int** flag){	if (word[n] == '\0')	{		return true;	}	flag[i][j] = 1;	//上下左右的顺序	if (i > 0 && flag[i-1][j]!=1 && board[i - 1][j] == word[n])	{		if (findNext(board, boardRowSize, boardColSize, i - 1, j, word, n + 1, flag))			return true;	}	if (i + 1 < boardRowSize && flag[i + 1][j] != 1 && board[i + 1][j] == word[n])	{		if (findNext(board, boardRowSize, boardColSize, i + 1, j, word, n + 1, flag))			return true;	}	if (j>0 && flag[i][j - 1] != 1 && board[i][j - 1] == word[n])	{		if (findNext(board, boardRowSize, boardColSize, i, j - 1, word, n + 1, flag))			return true;	}	if (j + 1

2.Subsets

  求子序列问题，看了答案

此题的数据是不重复的，可以不用排序的...当输入数长度为n时，每一位都只有两种情况，存在或不存在

当n=3时，如右图所示，还有一个类似地第一位不取的时候，树的叶子是我们要的结果，遍历flag得到答案

void sort(int *nums, int numsSize){	int j;	for (int increment = numsSize / 2; increment > 0; increment /= 2){		for (int i = increment; i
   
    = increment; j -= increment){				if (tmp < nums[j - increment])					nums[j] = nums[j - increment];				else					break;			}			nums[j] = tmp;		}	}}void getNsubsets(int *nums, int numsSize, int *flag, int i, int** ret, int* returnSize, int **columnSizes){	if (i == numsSize)	{		int *col = (int*)malloc(numsSize * (sizeof(int)));		int j, k, count = 0;		for (j = 0, k = 0; j < numsSize; j++){			if (flag[j] == 1)			{				col[k++] = nums[j];				count++;			}		}		ret[*returnSize] = col;		(*columnSizes)[*returnSize] = count;		(*returnSize)++;	}	else	{		flag[i] = 1; getNsubsets(nums, numsSize, flag, i + 1, ret, returnSize, columnSizes);		flag[i] = 0; getNsubsets(nums, numsSize, flag, i + 1, ret, returnSize, columnSizes);	}}int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {	int i, j;	*returnSize = 1;		for (i = 0; i < numsSize; i++){		(*returnSize) *= 2;	}	int **ret = (int**)malloc((*returnSize)*sizeof(int*));	int *columnS = (int*)malloc((*returnSize)*sizeof(int));	*columnSizes = columnS;	int *flag = (int *)calloc(numsSize,sizeof(int));//	*returnSize = 0;	sort(nums, numsSize);	getNsubsets(nums, numsSize, flag, 0, ret, returnSize, columnSizes);	return ret;}
   

3.Subsets II

数据重复时的情况，感觉有点难

比如122，画出左边的树，每一个节点都是我们要的结果；先排序，当前层cur和开始的下标index的关系饶了很久

void sort(int *nums, int numsSize){	int j;	for (int increment = numsSize / 2; increment > 0; increment /= 2){		for (int i = increment; i
   
    = increment; j -= increment){				if (tmp < nums[j - increment])					nums[j] = nums[j - increment];				else					break;			}			nums[j] = tmp;		}	}}void getNsubsetsWithDup(int *nums, int numsSize, int *flag, int cur,int index, int** ret, int* returnSize, int **columnSizes){	if (cur <=numsSize)	{		int *col = (int*)malloc((cur+1) * (sizeof(int)));		int j, k;		for (j = 0, k = 0; j < cur; j++, k++){			col[k] = flag[j];				}		ret[*returnSize] = col;		(*columnSizes)[*returnSize] = cur;		(*returnSize)++;			}    for (int i = index ; i < numsSize; i++){		if (i == index  || nums[i] != nums[i - 1])		{						flag[cur] = nums[i];					getNsubsetsWithDup(nums, numsSize, flag, cur + 1,i+1, ret, returnSize, columnSizes);				}	}}int** subsetsWithDup(int* nums, int numsSize, int** columnSizes, int* returnSize) {	int i, j;	*returnSize = 1;	for (i = 0; i < numsSize; i++){		(*returnSize) *= 2;	}	int **ret = (int**)malloc((*returnSize)*sizeof(int*));	int *columnS = (int*)malloc((*returnSize)*sizeof(int));	*columnSizes = columnS;	int *flag = (int *)calloc(numsSize, sizeof(int));	*returnSize = 0;	sort(nums, numsSize);	getNsubsetsWithDup(nums, numsSize, flag, 0,0, ret, returnSize, columnSizes);	return ret;}
   

交换的数据之后要交换回来，相当于是擦除动作，swap写复杂了，传入两个地址就行

void swap_ij(int *nums, int numsSize, int i, int j){	int tmp = nums[i];	nums[i] = nums[j];	nums[j] = tmp;}void permute_dfs(int*nums,int numsSize,int *returnSize,int **ret,int i){	if (i == numsSize - 1)	{		int *col = (int*)malloc(numsSize * sizeof(int));		memcpy(col, nums, numsSize*sizeof(int));		ret[*returnSize] = col;		(*returnSize)++;	}	for (int j = i; j < numsSize; j++)	{		swap_ij(nums, numsSize, i, j);				permute_dfs(nums, numsSize, returnSize, ret, i + 1);		swap_ij(nums, numsSize, i, j);	}}int** permute(int* nums, int numsSize, int* returnSize) {	*returnSize = 0;//	sort(nums, numsSize);	int length = 1;	for (int i = 1; i <= numsSize; i++){		length *= i;	}	int **ret = (int **)malloc(length * sizeof(int *));	int *col;	permute_dfs(nums, numsSize, returnSize, ret, 0);	return ret;}

5.Permutations II

还是和I一样画树，不过用set记录是否出现过，用C++简单些...

class Solution {public:	void swap_ij(vector
   
    & nums, int i, int j){		int tmp = nums[i];		nums[i] = nums[j];		nums[j] = tmp;	}	void permute_dfs(vector
    
     & nums, vector
     
      
       > &ret,int i){		if (i == nums.size() - 1)		{			ret.push_back(nums);			return;		}		unordered_set
       
         set;		for (int j = i; j < nums.size(); j++)		{			if (j == i || (nums[i] != nums[j] && set.find(nums[j])==set.end()))			{				set.insert(nums[j]);				swap_ij(nums, i, j);								permute_dfs(nums,  ret,i + 1);				swap_ij(nums, i, j);							}		}	}	vector
        
         
          > permuteUnique(vector
          
           & nums) { vector
           
            
             > ret; permute_dfs(nums, ret, 0); return ret; }};
            
           
          
         
        
       
      
     
    
   

6.N-Queens

基本上这里每道题都有多种解法，八皇后问题也可以看做是序列问题，可以用一个N维数组标记，总的来说都是回溯，我用的最傻的方法。II更简答

char **chessBoard(int n){	char ** ret = (char**)malloc(n*sizeof(char*));	for (int i = 0; i < n; i++)	{		ret[i] = (char*)malloc((n+1)*sizeof(char));		memset(ret[i], '.', n*sizeof(char));		ret[i][n] = '\0';	}	return ret;}//确定char[i][j]是Q还是.int isSafe(char** chess, int i, int j, int n){	if (j >= n)		return n;	int ii, jj;//row,column	for (jj = j; jj < n; jj++){		for (ii = 0; ii < i;  ii++){			if (chess[ii][jj] == 'Q')			{				break;			}		}		if (ii == i)		{			break;		}	}	if (jj == n)	{		return n;	}	//斜线	for (int k = 0; jj-k >= 0; k++){		if (ii >= k && chess[ii - k][jj - k] == 'Q')		{			jj=isSafe(chess, i, jj + 1, n);			return jj;		}	}	for (int k = 0; jj+k 
   
    = k && chess[ii - k][jj + k] == 'Q')		{			jj=isSafe(chess, i, jj + 1, n);			return jj;		}	}	if (jj == n)		return n;	return jj;}void backtrackingNQueens(int n, int i, int j, int *returnSize, char **map,char*** ret){	if (i == n)	{		char ** chess = chessBoard(n);//		memcpy(chess, map, n*sizeof(char*));		for (int k = 0; k < n; k++){	//		memcpy(chess[k], map[k], n*sizeof(char));			for (int j = 0; j < n; j++){				chess[k][j] = map[k][j];			}		}		ret[*returnSize] = chess;		(*returnSize)++;		return;	}	while ((j = isSafe(map, i,j, n)) != n)	{		map[i][j] = 'Q';		backtrackingNQueens(n, i + 1, 0, returnSize, map,ret);			map[i][j] = '.';		j++;	}	/*if ((j = isSafe(map, i, j+1, n)) != n)	{		backtrackingNQueens(n, i + 1, 0, returnSize, map, ret);	}*/	}char*** solveNQueens(int n, int* returnSize) {	*returnSize = 0;	//建一个棋盘	char ** map = chessBoard(n);	char ***ret = (char ***)malloc(1000 * sizeof(char**));	backtrackingNQueens(n, 0, 0, returnSize, map, ret);	return ret;}