77.组合

//理解回溯的原理及剪枝操作

    vector<vector<int>> result;vector<int> path;void backtracking(int n, int k, int start){if(path.size() == k){result.push_back(path);return;}for(int i = start; 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) {result.clear();path.clear();backtracking(n,k,1);return result;}

216.组合总和III

    vector<vector<int>> result;vector<int> path;void backtrace(int n, int k, int startIndex){if(path.size() == k){if(n == 0){result.push_back(path);}return;}for(int j = startIndex; j <= 9; j++){path.push_back(j);n -= j;backtrace(n,k,j+1);n += j;path.pop_back();}}vector<vector<int>> combinationSum3(int k, int n) {result.clear();path.clear();backtrace(n, k, 1);return result;}

17.电话号码的字母组合，需二刷

    const string letterMap[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:vector<string> result;string s;void backtracking(const string & digits, int start){if(start == digits.size()){result.push_back(s);return;}int digit = digits[start] - '0';string letter = letterMap[digit];for(int i = 0; i < letter.size(); i++){s.push_back(letter[i]);backtracking(digits, start+1);s.pop_back();}}vector<string> letterCombinations(string digits) {result.clear();s.clear();if(digits.size() == 0){return result;}backtracking(digits, 0);return result;}