Java Solution - DFS With Backtracking (no loops) - 2 MS


  • 1
    C
    public class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> set = Arrays.asList(1,2,3,4,5,6,7,8,9);
    
    void solver(int cur, List<Integer> subset, int k, int n){
        if(subset.size() == k && n == 0){
            List<Integer> temp = new ArrayList<Integer>();
            for(Integer i : subset)
                temp.add(i);
            res.add(temp);
            return;
        }
        if(cur == set.size() || subset.size() > k || n<0)
            return;
        subset.add(set.get(cur));
        solver(cur+1,subset,k,n-set.get(cur));
        subset.remove(subset.size()-1);
        solver(cur+1,subset,k,n);
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> subset = new ArrayList<Integer>();
        solver(0,subset,k,n);
        return res;
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.