AllenY's blog

LeetCode刷题记录（回溯篇），个人向。

[46] Permutations

难度：Medium
语言：C++

题目描述。
使用used来记录当前已使用的元素，尝试增加used，递归调用，记录path，在path长度达到nums.size()时将结果记录到result即可。

class Solution {
public:
  void backtracking(vector<int> &nums, vector<bool> &used, vector<int> &path,
                    vector<vector<int>> &result) {
    int size = nums.size();

    if (path.size() == size) {
      result.push_back(path);
      return;
    }

    for (int i = 0; i < size; ++i) {
      if (used[i]) {
        continue;
      }
      used[i] = true;
      path.push_back(nums[i]);
      backtracking(nums, used, path, result);
      path.pop_back();
      used[i] = false;
    }
    return;
  }
  vector<vector<int>> permute(vector<int> &nums) {
    vector<bool> used(nums.size(), false);
    vector<int> path;
    vector<vector<int>> result;
    backtracking(nums, used, path, result);
    return result;
  }
};

[78] Subsets

难度：Medium
语言：C++

题目描述。
相比上一题求全排列，这一题的不同点有二：

• 我们要求的是子集，单个集合不要求包含所有元素，因此在这棵递归树上，我们要求的不止是叶子节点，而是所有节点。因此不是在递归结束的时候记录结果，而是每次调用都记录一下结果。
• 相比全排列，集合对元素的顺序不再做要求。因此相比之前使用used数组，这里可以只记录startIndex，然后每次递归从startIndex往后遍历，来做到包含不同的元素组合。

class Solution {
  public:
    void backtracking(vector<int> &nums, int startIndex, vector<int> &path,
                      vector<vector<int>> &result) {
        int size = nums.size();
        result.push_back(path);
        for (int i = startIndex; i < size; ++i) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1, path, result);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int> &nums) {
        vector<int> path;
        vector<vector<int>> result;
        backtracking(nums, 0, path, result);
        return result;
    }
};

[17] Letter Combinations of a Phone Number

难度：Medium
语言：C++

题目描述。
构造一个mapping用来存数字到字母的映射，同时用mapping[digits[startIndex] - '2']来取这个映射。回溯部分和之前大同小异，更新一下startIndex，同时记录路径，最后加进result即可。

class Solution {
  public:
    const vector<string> mapping = {"abc", "def",  "ghi", "jkl",
                                    "mno", "pqrs", "tuv", "wxyz"};

    void backtracking(string &digits, int startIndex, string &path,
                      vector<string> &result) {
        int size = digits.size();
        if (startIndex >= size) {
            if (size > 0) {
                result.push_back(path);
            }
            return;
        }

        string chars = mapping[digits[startIndex] - '2'];
        int numChars = chars.size();

        for (int i = 0; i < numChars; ++i) {
            path.push_back(chars[i]);
            backtracking(digits, startIndex + 1, path, result);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> result;
        string path;
        backtracking(digits, 0, path, result);
        return result;
    }
};

[39] Combination Sum

难度：Medium
语言：C++

题目描述。
对回溯的代码逐渐熟练，同样是一次写出答案。
和之前的代码大同小异。这里因为candidates[i]是大于0的，所以出现new_sum == target就不用继续递归了。
当我们选择了某个数字，则以后的递归只会考虑该数字以及之后的数字，不再考虑之前的数字，这保证了结果的唯一性（不出现重复组合）。
这道题的关键在于数字是可以重复使用的，这里我们用递归参数所使用的index为i而不是i+1来体现。

class Solution {
  public:
    void backtracking(const vector<int> &candidates, const int target,
                      int index, int cur_sum, vector<int> &choosen,
                      vector<vector<int>> &result) {
        int size = candidates.size();
        if (index >= size) {
            return;
        }

        for (int i = index; i < size; ++i) {
            int new_sum = cur_sum + candidates[i];
            if (new_sum > target) {
                continue;
            }
            choosen.push_back(candidates[i]);
            if (new_sum == target) {
                result.push_back(choosen);
                // 0 will not appear in candidates, and 2 <= candidates[i] <= 40
                // so no need to backtrack further
            } else {
                backtracking(candidates, target, i, new_sum, choosen, result);
            }
            choosen.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<int> choosen;
        vector<vector<int>> result;
        backtracking(candidates, target, 0, 0, choosen, result);
        return result;
    }
};