216. Combination Sum III.md

216. Combination Sum III

---

leetcode-cn Daily Challenge on September 11th, 2020.

leetcode Daily Challenge on September 12th, 2020.

---

Difficulty : Medium

Related Topics : Array、Backtracking

---

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

• All numbers will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

---

Solution

• mine

  • Java

    same as 39. Combination Sum and 40. Combination Sum II.

    • Recursive & Backtrack Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.4 MB, less than 6.00% of Java online submissions

      public List<List<Integer>> combinationSum3(int k, int n) {
          int[] arr = new int[]{1,2,3,4,5,6,7,8,9};
          List<List<Integer>> res = new ArrayList<>();
          res = recursive(arr, n, 0, k);
          return res;
      }
      
      public List<List<Integer>> recursive(int[] arr, int target, int start, int count) {
          List<List<Integer>> res = new ArrayList<>();
      
          if (start >= arr.length || arr[start] > target) {
              return res;
          }
          if (target == arr[start]) {
              List<Integer> t = new ArrayList<>();
              t.add(arr[start]);
              if(t.size() == count){
                  res.add(t);
              }
              return res;
          }
      
          for (int j = start; j < arr.length; j++) {
              if (target == arr[j]) {
                  List<Integer> t = new ArrayList<>();
                  t.add(arr[j]);
                  if(t.size() == count){
                      res.add(t);
                  }
                  break;
              }
              List<List<Integer>> temp = recursive(arr, target - arr[j], j + 1, count-1);
              if (!temp.isEmpty()) {
                  for (List<Integer> t : temp) {
                      t.add(0, arr[j]);
                      if(t.size() == count){
                          res.add(t);
                      }
                  }
              }
          }
          return res;
      }
      

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.6 MB, less than 95.56% of Java online submissions

      public List<List<Integer>> combinationSum3(int k, int n) {
          List<List<Integer>> res = new LinkedList<>();
          if (k > 9
                  || n < k * (k + 1) / 2
                  || n > 45 - (9 - k) * (9 - k + 1) / 2) return res;
          helper(res, k, n, new ArrayList<>(), 1);
          return res;
      }
      
      void helper(List<List<Integer>> res, int size, int target, List<Integer> t, int start) {
          for (int i = start; i < 10; i++) {
              if (i > target) return;
              if (t.size() + 1 == size) {
                  if(target > 9) return;
                  List<Integer> temp = new ArrayList<>(t);
                  temp.add(target);
                  res.add(temp);
                  return;
              }
      
              t.add(i);
              helper(res, size, target - i, t, i + 1);
              t.remove(t.size() - 1);
          }
      }
      

---

• the most votes

• Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.7 MB, less than 6.00% of Java online submissions.

  Used backtracking to solve this.

  Build an array to apply to "subset" template. Each time we add an element to the "list", for the next step, target= target - num[i]. Since we have already added one element, for the next step, we can only add k-1 elements. Since no duplicated elements accept, for the next loop, the "start" should point to the next index of current index. The list.remove(list.size() - 1) here means, we need to change the element here. I know it is hard to understand it, let me give you an example.

  When k=3, n=9, my answer works like this:

  [1]->[1,2]->[1,2,3]. Since now sum is not 9, no more backtracking, so after list.remove(list.size() - 1), it is [1,2]. Then next follows [1,2,4], sum is not 9, repeat process above untill [1,2,6]. When go to next backtracking, the list will be added to result, and for this list, no more backtracking.

  Now we can go back to a previous backtracking, which is [1,3]->[1,3,4], fail. [1,4,]->[1,4,5], fail. And so one.

  So the point of list.remove(list.size() - 1) is, after each "fail" or "success", since we don't need to do further attempts given such a condition, we delete the last element, and then end current backtracking. Next step is, add the next element to the deleted index, go on attempting.

  public List<List<Integer>> combinationSum3(int k, int n) {
      int[] num = {1,2,3,4,5,6,7,8,9};
      List<List<Integer>> result = new ArrayList<List<Integer>>();
      helper(result, new ArrayList<Integer>(), num, k, n,0);
      return result;
  }
  
  public void helper(List<List<Integer>> result, List<Integer> list, int[] num, int k, int target, int start){
      if (k == 0 && target == 0){
          result.add(new ArrayList<Integer>(list));
      } else {
          for (int i = start; i < num.length && target > 0 && k >0; i++){
              list.add(num[i]);
              helper(result, list, num, k-1,target-num[i],i+1);
              list.remove(list.size()-1);
          }
      }
  }
  

---