Combination Sum III

1package pkg5leetcode.official75;2 3/*4 * Combination Sum III | LC 2165 * APPROACH: Backtracking choose k distinct digits sum to n.6 * COMPLEXITY: Time O(C(9,k)), Space O(k)7 */8import java.util.*;9 10public class official75_LC216CombinationSumIII {11    static List<List<Integer>> combinationSum3(int k, int n) {12        List<List<Integer>> res = new ArrayList<>();13        backtrack(1, k, n, new ArrayList<>(), res);14        return res;15    }16 17    static void backtrack(int start, int k, int remain, List<Integer> path, List<List<Integer>> res) {18        if (path.size() == k) {19            if (remain == 0) res.add(new ArrayList<>(path));20            return;21        }22        for (int d = start; d <= 9; d++) {23            if (remain < d) break;24            path.add(d);25            backtrack(d + 1, k, remain - d, path, res);26            path.remove(path.size() - 1);27        }28    }29 30    public static void main(String[] args) {31        List<List<Integer>> r = combinationSum3(3, 7);32        check(r.size() == 1 && r.get(0).equals(Arrays.asList(1,2,4)), "case1");33        check(combinationSum3(3, 9).size() == 3, "case2");34        System.out.println("all tests passed");35    }36 37    static void check(boolean cond, String name) {38        if (!cond) throw new AssertionError("FAILED: " + name);39        System.out.println("  PASS " + name);40    }41}