@@ -0,0 +1,1659 @@
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be%0A * used and each combination should be a unique set of numbers.%0A *%0A * Ensure that numbers within the set are sorted in ascending order.%0A *%0A * Example 1:%0A *%0A * Input: k = 3, n = 7%0A *%0A * Output:%0A *%0A * %5B%5B1,2,4%5D%5D%0A *%0A * Example 2:%0A *%0A * Input: k = 3, n = 9%0A *%0A * Output:%0A *%0A * %5B%5B1,2,6%5D, %5B1,3,5%5D, %5B2,3,4%5D%5D%0A *%0A * Tags: Array, Backtracking%0A * Similar Problems: (M) Combination Sum%0A */%0Apublic class CombinationSum3 %7B%0A%0A    public static void main(String%5B%5D args) %7B%0A        CombinationSum3 cs = new CombinationSum3();%0A        System.out.println(cs.combinationSum3(3, 7));%0A        System.out.println(cs.combinationSum3(3, 9));%0A    %7D%0A%0A    public List%3CList%3CInteger%3E%3E combinationSum3(int k, int n) %7B%0A        List%3CList%3CInteger%3E%3E ans = new ArrayList%3C%3E();%0A        backtrack(ans, new ArrayList%3C%3E(), k, 1, n);%0A        return ans;%0A    %7D%0A%0A    private void backtrack(List%3CList%3CInteger%3E%3E ans, List%3CInteger%3E comb, int k, int start, int n) %7B%0A        if (comb.size() %3E k) return; // no need to search in k+1 numbers%0A%0A        if (comb.size() == k && n == 0) %7B // combination found%0A            List%3CInteger%3E res = new ArrayList%3CInteger%3E(comb); // make a copy of the list%0A            ans.add(res);%0A            return;%0A        %7D%0A%0A        for (int i = start; i %3C= 9; i++) %7B%0A            if (n - i %3E= 0) %7B // n %3C i can be skipped%0A                comb.add(i);%0A                helper(ans, comb, k, i + 1, n - i);%0A                comb.remove(comb.size() - 1); // remove the last number added%0A            %7D%0A        %7D%0A    %7D%0A%7D%0A

add 216 combination sum 3