代码随想录算法训练营第二十二天|回溯算法part01

第77题. 组合

在单个集合1-n中，寻找所有个数为k的组合。
和所有递归一样，都有三部曲。

1. 确定参数与返回值
2. 确定终止条件
3. 单层逻辑
   首先，回溯算法的返回值一般是void，参数依照题目要求而增加，在这一题中，参数有n,k还有startIndex。
   终止条件是path的size等于k，将path存放在result中。
   单层逻辑就是将该层的值放到path中，然后递归，回溯。
   在这一题中，有一个可以剪枝的地方，就是当余下的量已经不能够大于k，那就不需要去递归了。

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }

        for (int i = startIndex; i <= n - (k - path.size()) + 1; ++i) {
            path.push_back(i);
            backtracking(n, k, i + 1);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

216.组合总和III

在单个集合1-9中，寻找所有个数为k且和为target的组合。
这一题与上题一样，除了终止条件中需要判断和是否为target。多了一个剪枝操作，就是当值已经大于target，直接返回。

class Solution {
public:
    int count;
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int k, int n, int startIndex) {
        if (path.size() == k) {
            if (count == n)
                result.push_back(path);
            return;
        }
        if (count >= n) {
            return;
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; ++i) {
            count += i;
            path.push_back(i);
            backtracking(k, n, i + 1);
            count -= i;
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return result;
    }
};
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

17.电话号码的字母组合

这一题是在多个集合中找所有可能的组合。
因此回溯算法的宽度是每个集合里面的个数，回溯算法的深度是集合的个数。
本题还有一个建立数字和字母之间映射的问题，使用string数组来进行映射。
参数是digits与index，index是用来记录遍历第几个集合。

class Solution {
public:
    vector<string> result;
    string letter;
    const string lettermap[10] = {"",    "",    "abc",  "def", "ghi",
                                  "jkl", "mno", "pqrs", "tuv", "wxyz"};

    void
    backtracing(const string& digits, int index) {
        if (index == digits.size()) {
            result.push_back(letter);
            return;
        }
        int digit = digits[index] - '0';
        string s = lettermap[digit];
        for (int i = 0; i < s.size(); ++i) {
            letter.push_back(s[i]);
            backtracing(digits, index + 1);
            letter.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) 
            return result;
        backtracing(digits, 0);
        return result;
    }
};
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