216. Combination Sum III

四刷 06/2022

Version #1 DFS with Backtracking

Time O(C(9, k) * k) -> 

O(

K!(9−K)!9!⋅K​)

Space O(k)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Combination Sum III.

Memory Usage: 39.9 MB, less than 88.39% of Java online submissions for Combination Sum III.

class Solution {

    public List<List<Integer>> combinationSum3(int k, int n) {

        List<List<Integer>> result = new ArrayList<>();

        dfs(1, k, n, new ArrayList<>(), result);

        return result;

    }

    private void dfs(int startNum, int k, int target, List<Integer> path, List<List<Integer>> result) {

        if (path.size() > k) {

            return;

        }

        if (target == 0 && path.size() == k) {

            result.add(new ArrayList<>(path));

            return;

        }

        

        for (int i = startNum; i <= 9; i++) {

            if (i > target) {

                break;

            }

            path.add(i);

            dfs(i + 1, k, target - i, path, result);

            path.remove(path.size() - 1);

        }

    }

}

三刷
100.00 %
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        if (k <= 0 || n <= 0) return result;
       
        helper(1, k, n, new ArrayList<>(), result);
        return result;
    }
    private void helper(int start, int count, int target, List<Integer> path, List<List<Integer>> result) {
        if (count == 0) {
            if (target == 0) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = start; i <= 9 && i <= target; i++) {
            path.add(i);
            helper(i + 1, count - 1, target - i, path, result);
            path.remove(path.size() - 1);
        }
    }
}



 58.11%
public class Solution {
    //k is #num
    //n is target
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (k <= 0 || n <= 0) return result;
        helper(k, n, 1, new ArrayList<Integer>(), result);
        return result;
    }
    //nums: 1, 2, 3, ... , 9
    public void helper(int k, int target, int start, List<Integer> path, List<List<Integer>> result) {
        if (k == 0) {
            if (target == 0) result.add(new ArrayList<Integer>(path));
            return;
        }
        for (int num = start; num <= 9; num++) {
            if (num > target) return;
            path.add(num);
            helper(k - 1, target - num, num + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

二刷

54.52 %
/*3layers
One layer choose 1 number from [1, 9]
The later layer's number must be greater than the previous layer in case of duplicate combinations
*/
public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        if (k <= 0 || n <= 0) return result;
        combinationSum3DfsHelper(k, n, 1, new ArrayList<Integer>(), result);
        return result;
    }
    private void combinationSum3DfsHelper(int count, int target, int start, List<Integer> path, List<List<Integer>> result) {
        if (target < 0 || count < 0) return;
        if (target == 0 && count == 0) {
            result.add(new ArrayList<Integer>(path));
        }
        for (int i = start; i <= 9; i++) {
            path.add(i);
            combinationSum3DfsHelper(count - 1, target - i, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}