【coding】回溯

Posted on   |   In ,   |   views

1. 八皇后

问题描述：
在一个8*8的矩形格子中排放8个皇后,要满足的条件包括: 任意两个皇后都不能在同一行/列/对角线(斜率等于1/-1). 要求编程给出所有第一行第一列有皇后的解 (注：解的输出用8个数字表示,如：基本解{1,5,8,6,3,7,2,4},其中’1’表示第一行第一列即(1,1)处有皇后, 后同)

思路：
跟穷举查不多，我们依次在每一行放一个皇后，而一行有八列，所以我们在放置一个皇后时，就要马上判断皇后放置的列是否符合条件，如果符合，我们就放置下一个皇后，如果不符合，我们就尝试着将皇后放置在下一列，接着像刚才一样判断皇后放置的列是否合法…如此循环，直到最后一列为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <math.h>
#include <stdio.h>
#include <iostream>
#define N 4
int queen[N] = {0},
    sum =
        0;  // 数组queen[N]的下标表示皇后所在的行，queen[N]其值表示皇后所在的列

/**
 * 打印八皇后图表形式
 */
void Paint() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (queen[i] == j)
                printf("■ ");  // 输出皇后
            else
                printf("□ ");
        }
        printf("\n");
    }
    printf("\n");
}

/**
 * 输出所有皇后坐标
 */
void PrintfPutQueen() {
    for (int i = 0; i < N; i++) {
        printf("(%d,%d) ", i, queen[i]);
    }
    printf("\n");
}

int CanPlace(int row) {
    for (int j = 0; j < row;
         j++) {  // 将第 row 行皇后与前面所有行的皇后进行比较
        if (queen[row] == queen[j] ||
            abs(queen[j] - queen[row]) ==
                (row - j))  // 检查横排和对角线上是否可以放置皇后
            return 0;       // 不能放置皇后
    }
    return 1;  // 可以放置皇后
}

/**
 * 放置皇后
 */
void PutQueen(int row) {
    if (row >= N) {  //皇后已经全部放完时
        Paint();
        sum++;
        //		return;
    } else {
        for (int i = 0; i < N; i++) {  // 总共有N列，一列一列的试探放置皇后
            queen[row] = i;         // 将第row行皇后放在第 i 列上面
            if (CanPlace(row)) {    // 判断是否可以放置该皇后
                PutQueen(row + 1);  // 放下一个行皇后
            }
        }
    }
}

int main() {
    PutQueen(0);  //从横坐标为 0开始依次尝试
    printf("\nSum = %d\n", sum);
    return 0;
}

不使用全局变量方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>
#define N 8

/**
 * 打印八皇后图表形式
 */
void Paint(int *queen) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (queen[i] == j)
                printf("■ ");  // 输出皇后
            else
                printf("□ ");
        }
        printf("\n");
    }
    printf("\n");
}

/**
 * 输出所有皇后坐标
 */
void PrintfPutQueen(int *queen) {
    for (int i = 0; i < N; i++) {
        printf("(%d,%d) ", i, queen[i]);
    }
    printf("\n");
}

int CanPut(int row, int *queen) {
    for (int i = 0; i < row;
         i++) {  // 将第 row 行皇后与前面所有行的皇后进行比较
        if (queen[row] == queen[i] ||
            (abs(queen[row] - queen[i]) ==
             (row - i)))  // 检查横排和对角线上是否可以放置皇后
            return 0;     // 不能放置皇后
    }
    return 1;  // 可以放置皇后
}

/**
 * 放置皇后
 */
int PutQueen(int row, int *queen) {
    int sum = 0;
    if (row >= N) {  // 说明皇后都已经放好了
        Paint(queen);
        return 1;
    } else {
        for (int i = 0; i < N; i++) {  // 总共有N列，一列一列的试探放置皇后
            queen[row] = i;            // 将第row行皇后放置在第i列
            if (CanPut(row, queen)) {  // 判断是否可以放置该皇后
                sum += PutQueen(row + 1, queen);  // 放下一个行皇后
            }
        }
    }
    return sum;
}

int main() {
    // 数组queen[N]的下标表示皇后所在的行，queen[N]其值表示皇后所在的列
    int queen[N] = {0}, sum = 0;
    sum = PutQueen(0, queen);
    printf("Sum = %d\n", sum);
    return 0;
}

2. 2n皇后

问题描述：
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。
现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

思路：
其实就是在n皇后基础上改进的，按照n皇后思想，先放黑的，黑的都放好后再放白的，就是要多加一个
判断已经放了黑的的位置就不能再放白的了。

输入格式
　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数
（如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后）

输出格式
　　输出一个整数，表示总共有多少种放法。

样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2

样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * Creation         :       2019.04.04 14:50
 * Last Reversion   :       2019.03.04 15:22
 * Author           :       Lingyong Smile {smilelingyong@163.com}
 * File Type        :       cpp
 * -----------------------------------------------------------------
 * EightQueen(2n皇后问题)

 * -----------------------------------------------------------------
 * Crop right @ 2019 Lingyong Smile {smilelingyong@163.com}
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int white[10], black[10], a[10][10], sum = 0, N = 0;

int CanPlaceBlack(int row) {
    for (int i = 0; i < row; i++) {
        if (black[row] == black[i] || (abs(black[row] - black[i]) == (row - i)))
            return 0;
    }
    return 1;
}

int CanPlaceWhite(int row) {
    for (int i = 0; i < row; i++) {
        if (white[row] == white[i] || (abs(white[row] - white[i]) == (row - i))) 
            return 0;
    }
    return 1;
}

void PutWhite(int row) {
    if (row >= N) {
        sum++;
    } else {
        for (int i = 0; i < N; i++) {
            white[row] = i;
            if (a[row][i] == 0 || black[row] == white[row]) // 该位置不能放或者已经放了黑的
                continue;
            if (CanPlaceWhite(row)) {
                PutWhite(row + 1);
            }
        }
    }
}

void PutBlack(int row) {
    if (row >= N) {
        PutWhite(0);
    } else {
        for (int i = 0; i < N; i++) {
            black[row] = i;
            if (a[row][i] == 0)
                continue;
            if (CanPlaceBlack(row)) {
                PutBlack(row + 1);
            }
        }
    }
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    PutBlack(0);
    printf("Sum = %d\n", sum);    
    return 0;
}

3. 国际象棋

题目描述：
​ 假设国际象棋盘有5*5共有25个格子。设计一个程序，使棋子从初试位置（棋盘格编号为1的位置）开始跳马，能够把棋盘的格子全部走一遍，每个格子只允许走一次，要求：
​ （1）输出一个解（用二维数组来记录马跳的过程，即【步号，棋盘格编号】，左上角为第1步起点）
​ （2）求总共有多少解？
棋盘格编号为：
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

思想：
​ 回溯思想 (和八皇后一个思路，都是要走完整个棋盘，即递归出口条件是类似的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
int a[5][5];                                // 棋盘
int b[5][5] = {0};                          // 用于标记棋盘对应位置是否已走过
int step[25] = {0}, step_num = 0, sum = 0;  // 用于记录每步走过的位置，sum为总共有多少总跳法
                                           
void Init(int a[][5]) {                     // 初始化棋盘
    int k = 1;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            a[i][j] = k++;
        }
    }
}

/**
 * 判断该跳是否可行
 */
int Check(int x, int y) {
    if (x < 0 || x >= 5 || y < 0 || y >= 5 || b[x][y] == 1)  // 不要忘了判断该位置是否已走过
        return 0;
    else
        return 1;
}

/**
 * 探寻可走的路
 */
void Search(int x, int y) {
    if (Check(x, y)) {               // 如果该跳可行
        step[step_num++] = a[x][y];  // step下标从1开始
        if (step_num == 25) {        // 若25个均跳好了
            sum++;
            printf("\nThe %d Jump:\n", sum);
            for (int i = 0; i < step_num; i++) {
                printf("[%d,%d]\n", i + 1, step[i]);
            }
        }
        b[x][y] = 1;                // 标记该位置已经走过了
        Search(x + 1, y + 2);       // 递归调用，寻找下一跳
        Search(x + 1, y - 2);
        Search(x - 1, y + 2);
        Search(x - 1, y - 2);
        Search(x + 2, y + 1);
        Search(x + 2, y - 1);
        Search(x - 2, y + 1);
        Search(x - 2, y - 1);
        step_num--;                 // 若寻找的下一跳都不可行，取消这一步，回退到上一步
        b[x][y] = 0;                // 把这步设置标记未走过
    }
}

int main() {
    Init(a);                        // 初始化棋盘
    Search(0, 0);
    printf("\nSum = %d", sum);
    return 0;
}

4. 马跳日

题目描述：
​ 在半个中国象棋棋盘上,马在左下角(1, 1)处, 马走日字，而且只能往右走，
不能向左，可上可下，求从起点到(m, n)处有几种不同的走法（函数的递归调用）
其中，1<= m <=5， 1<= n <=9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

int horse(int x1, int y1, int x2, int y2) {
    int sum = 0;
    if (y1 > y2 || (y1 == y2 && x1 != x2))  // 起点和终点不能在同一列
        return 0;
    else if (x1 == x2 && y1 == y2)  		// 走到了终点，返回1，然后递归回去
        return 1;
    else {
        if (x1 - 1 >= 1 && y1 + 2 <= 9) sum += horse(x1 - 1, y1 + 2, x2, y2);
        if (x1 - 2 >= 1 && y1 + 1 <= 9) sum += horse(x1 - 2, y1 + 1, x2, y2);
        if (x1 + 2 <= 5 && y1 + 1 <= 9) sum += horse(x1 + 2, y1 + 1, x2, y2);
        if (x1 + 1 <= 5 && y1 + 2 <= 9) sum += horse(x1 + 1, y1 + 2, x2, y2);
        return sum;
    }
}

int main() {
    int m, n;
    printf("请输入目的地址：\n");
    scanf("%d %d", &m, &n);
    printf("目的结果数为%d\n", horse(1, 1, m, n));
    return 0;
}

5. 骑士最短路径

问题描述：
​ 在一个8*8的矩形格子中找起始位置 start(x, y) 到 终点位置 end(x, y) 的最短路径。
输出最短的路径长度，并输出路径顺序点（这部分没有完成）
思路：
​ 使用BFS思想(类似于层次遍历)，单源最短路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
using namespace std;
#include <queue>

typedef struct Point {
    int x;
    int y;
} Point;

// 定义马日跳
int direction[][2] = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1},
                      {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};

int BFS(Point start, Point end) {
    int step[8][8] = {0};                       // 存放起始点到达8x8网格每一点时刻走的步数
    Point cur, next;
    queue<Point> que;
    que.push(start);                            // 起始点入队
    while (!que.empty()) {                      // 当队列不为空
        cur = que.front();                      // 队首元素出队
        que.pop();
        if (cur.x == end.x && cur.y == end.y) {// 跳到终点时，返回当前走的路径长度，即为最短路径
            return step[cur.x][cur.y];
        }
        for (int i = 0; i < 8; i++) {           // 没跳到终点，继续遍历当前位置的下一跳
            next.x = cur.x + direction[i][0];
            next.y = cur.y + direction[i][1];
            if (next.x < 1 || next.x > 8 || next.y < 1 || next.y > 8) continue;
            if (step[next.x][next.y] == 0) {    // 若当前点未被访问，则将其加入队列
                step[next.x][next.y] = step[cur.x][cur.y] + 1;
                que.push(next);
            }
        }
    }
}

int main() {
    Point start, end;
    cin >> start.x >> start.y;
    cin >> end.x >> end.y;
    cout << "The shortest path length is " << BFS(start, end) << endl;
}

6. 矩阵中的路径

题目描述
​ 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符
的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，
向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能
再次进入这个格子。 例如上图：abtgcfcsjdeh 这样的3 X 4 矩阵中包
含一条字符串“bfce”的路径，但是矩阵中不包含“abfb”路径，因为字符串的第一
个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
输入：
3
4
abtgcfcsjdeh
bfce
abfb
输出：
1
0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstring>  
#include <string>  
using namespace std;

#define MAX_SIZE 1000
/**
 * 思想：
 *    当矩阵坐标中为(row, col)的格子和路径字符串中下标为pathLength的字符串一样时，并且
 * 该格子未被访问时，则从4个相邻的格子(row, col-1)、(row, col+1)、(row-1, col)、(row+1, col)
 * 中去定位路径字符串中下标为pathLength+1的字符。
 *    如果4个相邻的格子都没有匹配字符串中下标为pathLength+1的字符，则表明当前路径字符串中
 * 下标为pathLength的字符在矩阵中定位不正确，我们需要回到前一个字符(pathLength-1)，然后重新定位。
 *    一直重复这个过程，知道路径字符串上的所有字符都在矩阵中找到合适的位置（此时 str[pathLength] == '\0'）
 */ 
bool Judge(const char *matrix, int rows, int cols, int row, int col, 
                const char *str, int pathLength, bool *visited) {
    // 遍历完路径字符串，说明路径字符串上的所有字符都在矩阵中找到合适的位置了
    if (str[pathLength] == '\0')  
        return true;
    
    bool hasPath = false;
    int index = row * cols + col;  
    if (row >= 0 && row < rows && col >= 0 && col < cols 
            && matrix[index] == str[pathLength]
                && !visited[index]) {    // str[pathLength]字符找到了
        visited[index] = true;           // 并将找到的这个矩阵元素标识为已访问
        hasPath = Judge(matrix, rows, cols, row, col-1, str, pathLength+1, visited)
               || Judge(matrix, rows, cols, row, col+1, str, pathLength+1, visited)  
               || Judge(matrix, rows, cols, row-1, col, str, pathLength+1, visited) 
               || Judge(matrix, rows, cols, row+1, col, str, pathLength+1, visited);
        // 没有匹配，回退上一个位置
        visited[index] = false;
    }
    return hasPath;
}

bool hasPath(char *matrix, int rows, int cols, char *str) {
    if (matrix == NULL || rows < 1 || cols < 1 || str == NULL) 
        return false;
    // 创建一个bool类型的动态数组，返回数组的第一个元素类型的指针
    bool *visited = new bool[rows * cols];  
    memset(visited, 0, rows * cols);        // 将bool数组元素都初始化为0，即false

    int pathLength = 0;                     // 路径字符串下标
    for (int row = 0; row < rows; ++row) {
        for (int col = 0; col < cols; ++col) {
            if (Judge(matrix, rows, cols, row, col, str, pathLength, visited)) {
                return true;
            }
        }
    }

    delete[] visited;
    return false;
}

int main() {
    char matrix[MAX_SIZE], str[MAX_SIZE];
    int rows, cols, res;
    printf("Please input the row number:\n");
    scanf("%d", &rows);
    printf("Please input the col number:\n");
    scanf("%d", &cols);
    getchar();                  // 读取缓冲区中的回车
    printf("Please input the matrix:\n");
    scanf("%s", matrix);        
    printf("Please input the search path:\n");
    getchar();                  // 读取缓冲区中的回车
    scanf("%s", str);
    res = hasPath(matrix, rows, cols, str);
    if (res) {
        printf("Matirx has this path!\n");
    } else {
        printf("Matirx do not has this path!\n");
    }
    // getchar();
    return 0;
}

7. 机器人的运动范围

题目描述
​ 地上有一个m行和n列的方格。一个机器人从坐标0, 0的格子开始移动，每一次只能
向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k
的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路：
​ 回溯的思想（类似于DFS深度优先搜索，先序遍历，结合国际象棋看）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
#include <stdlib.h>

/**
 * 计算整数各位之和
 */
int GetDigistSum(int number) {
    int sum = 0;
    while (number) {
        sum += (number % 10);
        number /= 10;
    }
    return sum;
}

/**
 * DFS 深度优先遍历
 */ 
int Moving(int threshold, int rows, int cols, int x, int y, int *visited) {
    int count = 0;
    if (x >= 0 && x < rows && y >= 0 && y < cols 
            && (GetDigistSum(x) + GetDigistSum(y)) <= threshold 
                && visited[x * cols + y] == 0) {
        visited[x * cols + y] = 1;
        count = 1 + Moving(threshold, rows, cols, x-1, y, visited)
                  + Moving(threshold, rows, cols, x+1, y, visited)
                  + Moving(threshold, rows, cols, x, y-1, visited)
                  + Moving(threshold, rows, cols, x, y+1, visited);
    }
    return count;
}

/**
 * 初始化访问标志矩阵，并从 (0, 0) 开始遍历
 */ 
int MovingCount(int threshold, int rows, int cols) {
    if (threshold < 0 || rows < 0 || cols < 0)
        return 0;
    int *visited = (int*)malloc(sizeof(int) * rows * cols);
    for (int i = 0; i < rows * cols; i++) 
        *(visited + i) = 0;
    int count = Moving(threshold, rows, cols, 0, 0, visited);
    free(visited);
    return count;
}

int main() {
    int rows, cols, threshold = 18;
    scanf("%d %d", &rows, &cols);
    scanf("%d", &threshold);
    printf("%d\n", MovingCount(threshold, rows, cols));
    return 0;
}

8. 全排列 [leetcode-46]

123的全排列有123、132、213、231、312、321这六种。首先考虑213和321
这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后
可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231
和312。因此可以知道——全排列就是从第一个数字起每个数分别与它后面的数字交
换。找到这个规律后，递归的代码就很容易写出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
/* 交换两个数据 */
void Swap(int* a, int* b) {
    int c = *a;
    *a = *b;
    *b = c;
}

void FullyArrange(int str[], int index, int str_len) {
    if (index == str_len) {
        /* 输出当前的排列 */
        for (int i = 0; i < str_len; i++) {
            printf("%d ", str[i]);
        }
        printf("\n");
    } else {
        for (int j = index; j < str_len; j++) {     // 第index个数分别与它后面的数字交换就能得到新的排列
            Swap(&str[index], &str[j]);
            FullyArrange(str, index + 1, str_len);
            Swap(&str[index], &str[j]);             // 保证每一层递归后保持上一层的顺序  
        }
    }
}
int main() {
    int a[] = {1, 2, 3};
    int str_len = sizeof(a) / sizeof(int);
    FullyArrange(a, 0, str_len);
    return 0;
}

9. 全排列II [leetcode-47]

给定一个可包含重复数字的序列，返回所有不重复的全排列。

输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <set>
using namespace std;

void Swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void permuteUniqueDFS(vector<int> &nums, int index, set<vector<int>> &res_set) {
    if (index == nums.size()) {
        res_set.insert(nums);
    }
    for (int i = index; i < nums.size(); i++) {
        Swap(nums[i], nums[index]);
        permuteUniqueDFS(nums, index + 1, res_set);
        Swap(nums[i], nums[index]);
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> res;
    set<vector<int>> res_set;
    permuteUniqueDFS(nums, 0, res_set);
    for (set<vector<int>>::iterator iter = res_set.begin(); iter != res_set.end(); iter++) {
        res.push_back(*iter);
    }
    return res;
}

int main() {
    vector<int> nums;
    int x;
    while (cin >> x && x != -1) {
        nums.push_back(x);
    }
    vector<vector<int>> res = permuteUnique(nums);
    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;
}

10. 组合 [leetcode-77]

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
using namespace std;

/**
 * 像这种要求出所有结果的集合，一般都是用DFS调用递归来解(结合全排列等)
 */ 
void DFS(int n, int k, int level, vector<int> &out, vector<vector<int>> &res) {
    if (out.size() == k) {
        res.push_back(out);
        return;
    }
    for (int i = level; i <= n; i++) {
        out.push_back(i);
        DFS(n, k, i + 1, out, res);
        out.pop_back();
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;
    vector<int> out;
    DFS(n, k, 1, out, res);
    return res;
}


int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> nums = combine(n, k);
    for (vector<vector<int>>::iterator iter = nums.begin(); iter != nums.end(); iter++) {
        vector<int>::iterator it = (*iter).begin();
        for (; it != (*iter).end(); it++) {
            cout << *it << " ";
        }
        cout << endl;
    }
    return 0;
}

11. 电话号码字母组合 [leetcode-17]

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

思路：
​ 我们用递归 Recursion 来解，我们需要建立一个字典，用来保存每个数字所代表的字符串，
然后我们还需要一个变量 level，记录当前生成的字符串的字符个数，实现套路和上述那些
题十分类似。在递归函数中我们首先判断 level，如果跟 digits 中数字的个数相等了，
我们将当前的组合加入结果 res 中，然后返回。否则我们通过 digits 中的数字到 dict
中取出字符串，然后遍历这个取出的字符串，将每个字符都加到当前的组合后面，并调用递归
函数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void letterCombinationsDFS(string &digist, vector<string> &dict, int index, string out, vector<string> &res) {
    if (index == digist.size()) {
        res.push_back(out);
        return;
    }
    string str = dict[digist[index] - '0'];
    for (int i = 0; i < str.size(); i++) {
        letterCombinationsDFS(digist, dict, index + 1, out + str[i], res);
    }
}

vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
    vector<string> res;
    vector<string> dict{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    letterCombinationsDFS(digits, dict, 0, "", res);
}

int main() {
    string digits;
    cin >> digits;
    vector<string> res = letterCombinations(digits);
    for (vector<string>::iterator iter = res.begin(); iter != res.end();
         iter++) {
        cout << *iter << endl;
    }
    return 0;
}

12. 组合总和 [leetcode-39]

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]]

示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]]

思路：和组合，排列的那些题目都是一个套路
​ 需要另写一个递归函数，这里我们新加入三个变量，index记录当前的递归到的下标，out为一个解，res保存所有已经得到的解，每次调用新的递归函数时，此时的target要减去当前数组的的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <string>
using namespace std;

void combinationSumDFS(vector<int> candidates, int target, int index, vector<int> &out, vector<vector<int>> &res) {
    if (target < 0) return;
    if (target == 0) {
        res.push_back(out);
        return;
    }
    for (int i = index; i < candidates.size(); i++) {
        out.push_back(candidates[i]);
        combinationSumDFS(candidates, target - candidates[i], i, out, res);
        // 注意，这里传入的是 i 而不是 index，保证以前重复使用过的不再回溯使用，即保证没有重复的组合
        out.pop_back();     // 如果加上下一个之后大于target了，则回溯到上一步
    }

}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> out;
    combinationSumDFS(candidates, target, 0, out, res);
    return res;
}

int main() {
    vector<vector<int>> res;
    vector<int> candidates;
    int target, x;
    while (cin >> x && x != -1) {
        candidates.push_back(x);
    }
    cin >> target;
    res = combinationSum(candidates, target);
    for (int i = 0; i < res.size(); i++) {
        cout << "[";
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << "]" << endl;
    }
    return 0;
}

13. 组合总和II [leetcode-40]

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使
数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]]

思路：和组合，排列的那些题目都是一个套路
​ 需要另写一个递归函数，这里我们新加入三个变量，index记录当前的递归到的下标，
out为一个解，res保存所有已经得到的解，每次调用新的递归函数时，此时的target
要减去当前数组的的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void combinationSum2DFS(vector<int> &candidates, int target, int index, vector<int> &out, vector<vector<int>> &res) {
    if (target < 0) return;
    if (target == 0) {
        res.push_back(out);
        return;
    }
    for (int i = index; i < candidates.size(); i++) {
        if (i > index && candidates[i] == candidates[i-1]) continue; // 保证res中没有重复的
        out.push_back(candidates[i]);
        combinationSum2DFS(candidates, target - candidates[i], i + 1, out, res); 
        // i + 1，就不会重复使用当前数字了
        out.pop_back();
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> out;
    sort(candidates.begin(), candidates.end());
    combinationSum2DFS(candidates, target, 0, out, res);
    return res;
}

int main() {
    vector<vector<int>> res;
    vector<int> candidates;
    int target, x;
    while (cin >> x && x != -1) {
        candidates.push_back(x);
    }
    cin >> target;
    res = combinationSum2(candidates, target);

    for (vector<vector<int>>::iterator iter = res.begin(); iter != res.end(); iter++) {
        cout << "[";
        for (vector<int>::iterator it = (*iter).begin(); it != (*iter).end(); it++) {
            cout << *it << " ";
        }
        cout << "]" << endl;
    }
    return 0;
}

14. 组合总和III [leetcode-216]

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：
所有数字都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
using namespace std;

void combinationSum3DFS(int k, int target, int index, vector<int> &out, vector<vector<int>> &res) {
    if (target < 0) return;
    if (target == 0 && out.size() == k) {
        res.push_back(out);
        return;
    }
    for (int i = index; i <= 9; i++) {
        out.push_back(i);
        combinationSum3DFS(k, target - i, i + 1, out, res); // 注意，这里要传入 i + 1,保证不使用重复的元素
        out.pop_back();
    }
}

vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> res;
    vector<int> out;
    combinationSum3DFS(k, n, 1, out, res);
    return res;
}

int main() {
    int k, n;
    cin >> k >> n;
    vector<vector<int>> res = combinationSum3(k, n);
    for (vector<vector<int>>::iterator iter = res.begin(); iter != res.end(); iter++) {
        cout << "[";
        for (vector<int>::iterator it = (*iter).begin(); it != (*iter).end(); it++) {
            cout << *it << " ";
        }
        cout << "]" << endl;
    }
    return 0;
}

15. 子集 [leetcode-78]

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

输入: nums = [1,2,3]
输出:
[
[3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []]

思想：
​ 其实就是将长度为0-nums.size() 长度的组合都列出来就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
using namespace std;

void subsetsDFS(vector<int> &nums, int index, int target_size, vector<int> &out, vector<vector<int>> &res) {
    if (out.size() == target_size) {
        res.push_back(out);
        return;
    }
    for (int i = index; i < nums.size(); i++) {
        out.push_back(nums[i]);
        subsetsDFS(nums, i + 1, target_size, out, res);
        out.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> out;
    res.push_back({});
    for (int i = 1; i <= nums.size(); i++) {
        subsetsDFS(nums, 0, i, out, res);
    }
    return res;
}

int main() {
    vector<vector<int>> res;
    vector<int> nums;
    int x;
    while (cin >> x && x != -1) {
        nums.push_back(x);
    }
    res = subsets(nums);
    for (vector<vector<int>>::iterator iter = res.begin(); iter != res.end(); iter++) {
        cout << "[";
        for (vector<int>::iterator it = (*iter).begin(); it != (*iter).end(); it++) {
            cout << *it << " ";
        }
        cout << "]" << endl;
    }
    return 0;
}