image.png

思路：回溯 + 剪枝

  • 此题是经典的“以数组最后一个元素作为叶子节点”的组合类型回溯问题
  • 每个数字最多只可以用一次，所以循环从cur_index开始循环
  • 脑子里面要有图，这题就不画了，可以看其他类似题目中画的图

  • 优化剪枝：sum == k的时候就开始返回。

    代码：

    1. class Solution {
    2. public:
    3.   void backTrace(vector<vector<int>>& combina_vector ,vector<int>& cur_combina, int cur_index , int k, int n) {
    4.       if (cur_index > 10) {
    5.           return;
    6.       } 
    8.       if (cur_combina.size() == k) {
    9.           // cout << accumulate(cur_combina.begin(), cur_combina.end(), 0) << endl;
    10.           if (accumulate(cur_combina.begin(), cur_combina.end(), 0) == n) {
    11.               combina_vector.push_back(cur_combina);
    12.           }
    13.           return;
    14.       }
    16.       for (int i = cur_index ;i <= 9; i++) {
    17.           cur_combina.push_back(i);
    18.           backTrace(combina_vector, cur_combina, i + 1, k, n);
    19.           cur_combina.pop_back();
    20.       }
    21.   }
    22.   vector<vector<int>> combinationSum3(int k, int n) {
    23.       vector<vector<int>> combina_vector;
    24.       vector<int> cur_combina;
    25.       backTrace(combina_vector, cur_combina, 1, k, n);
    26.       return combina_vector;
    27.   }
    28. };