216. 组合总和 III

同组合，终止条件为：

  1. 元素个数是否等于k
  2. 元素和是否等于目标数

image.png

  1. class Solution {
  2. public:
  3.     vector<int> res;
  4.     vector<vector<int>> result;
  5.     int sum=0;
  6.     void backtracking(int k, int n,int startIndex)
  7.     {
  8.         if (res.size() == k) {
  9.             if (sum == n) result.push_back(res);
  10.             return; // 如果path.size() == k 但sum != targetSum 直接返回
  11.         }
  12.         for(int i =startIndex;i<=9;i++)
  13.         {
  14.            res.push_back(i);
  15.            sum+=i;
  16.            backtracking(k,n,i+1); 
  17.            sum-=i;
  18.            res.pop_back();
  19.         }
  20.     }
  21.     vector<vector<int>> combinationSum3(int k, int n) {
  22.         backtracking(k,n,1);
  23.         return result;
  24.     }
  25. };

剪枝优化

  1. 元素个数不能超过k 9-（k-pathsize()）+1
  2. 元素之和不能超过n