package com.fishercoder.solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * 216. Combination Sum III
 *
 * 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.


 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]]*/
public class _216 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList();
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        backtracking(k, n, nums, 0, new ArrayList(), result);
        return result;
    }

    void backtracking(int k, int n, int[] nums, int start, List<Integer> curr, List<List<Integer>> result) {
        if (n > 0) {
            for (int i = start; i < nums.length; i++) {
                curr.add(nums[i]);
                backtracking(k, n - nums[i], nums, i + 1, curr, result);
                curr.remove(curr.size() - 1);
            }
        } else if (n == 0 && curr.size() == k) {
            result.add(new ArrayList(curr));
        }
    }
}

@@ -298,17 +298,16 @@
 mbers.%0A%0A
-%0A
  Example
@@ -310,17 +310,16 @@
 mple 1:%0A
-%0A
  Input: 
@@ -331,25 +331,24 @@
 , n = 7%0A
-%0A
  Output:
 %0A%0A %5B%5B1,2
@@ -335,26 +335,24 @@
 = 7%0A Output:
-%0A%0A
  %5B%5B1,2,4%5D%5D%0A%0A
@@ -363,17 +363,16 @@
 mple 2:%0A
-%0A
  Input: 
@@ -384,25 +384,24 @@
 , n = 9%0A
-%0A
  Output:
 %0A%0A %5B%5B1,2
@@ -392,18 +392,16 @@
  Output:
-%0A%0A
  %5B%5B1,2,6
@@ -420,16 +420,18 @@
 %5B2,3,4%5D%5D
+%0A 
 */%0Apubli
@@ -446,16 +446,56 @@
 _216 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -557,16 +557,20 @@
         
+    
 List%3CLis
@@ -615,16 +615,20 @@
         
+  
+  
 int%5B%5D nu
@@ -670,16 +670,20 @@
  8, 9%7D;%0A
+    
         
@@ -744,16 +744,20 @@
         
+ 
+   
 return r
@@ -771,11 +771,19 @@
     
-%7D%0A%0A
+    %7D%0A%0A    
     
@@ -883,24 +883,28 @@
 %3E result) %7B%0A
+    
         if (
@@ -924,16 +924,20 @@
         
+    
 for (int
@@ -984,24 +984,28 @@
             
+   
+ 
 curr.add(num
@@ -1011,16 +1011,20 @@
 ms%5Bi%5D);%0A
+    
         
@@ -1100,24 +1100,28 @@
             
+  
+  
 curr.remove(
@@ -1146,24 +1146,28 @@
             
+    
 %7D%0A        %7D 
@@ -1164,16 +1164,20 @@
         
+ 
+   
 %7D else i
@@ -1205,24 +1205,28 @@
 e() == k) %7B%0A
+    
             
@@ -1258,16 +1258,30 @@
 curr));%0A
+            %7D%0A
         

refactor 216