LeetCode(108) -- 216

P216. Combination Sum III (Medium)

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.

My Solution

public class P216_CombinationSumIII {
    List<List<Integer>> ans = new ArrayList<>();
    Set<List<Integer>> set = new HashSet<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(new ArrayList<>(), k, n, new boolean[9]);
        return ans;
    }

    private void backtrack(List<Integer> tempList, int k, int n, boolean[] used) {
        if (k == 0 && n == 0) {
            ArrayList<Integer> newList = new ArrayList<>(tempList);
            Collections.sort(newList);
            if (set.contains(newList)) {
                return;
            }
            ans.add(newList);
            set.add(newList);
            return;
        }
        if (k <= 0 || n <= 0) {
            return;
        }
        for (int i = 0; i < 9; i++) {
            if (!used[i]) {
                used[i] = true;
                tempList.add(i + 1);
                backtrack(tempList, k - 1, n - i - 1, used);
                tempList.remove(tempList.size() - 1);
                used[i] = false;
            }
        }
    }
}

8%

The Best Solution

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        dfs(res, temp, k, n, 1);
        return res;
    
    }
    private void dfs(List<List<Integer>> res, List<Integer> temp, int k, int n, int start){
        if( k == 0|| n==0){
            if( k == 0 && n==0){
                res.add(new ArrayList<>(temp));
                return;
            }
            return;
        }
        for(int i = start; i <= 9; i ++){
            if(i<=n){
                temp.add(i);
                dfs(res, temp, k-1, n-i, i+1);
                temp.remove(temp.size()-1);
            }
        }
    }
}