2ms solution, easy to understand


  • 1
    Y
      public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (k == 0 || n == 0) return result;
        List<Integer> sequence = new ArrayList<Integer>();
        DFS(k, n, result, sequence, 1, 0);
        return result;        
    }
    public void DFS(int k, int n, List<List<Integer>> result, List<Integer> sequence, int start,
            int sum) {
        if (sum > n) return;
        if (sum == n && k == 0){
            result.add(new ArrayList<Integer>(sequence));
            return;
        }
        for (int i = start; i <= 9; i++) {
    	    sequence.add(i);
    	    sum += i;
    	    DFS(k-1, n, result, sequence, i+1, sum);//
    	    sequence.remove(sequence.size() - 1);
    	    sum -= i;
            }
    }

Log in to reply
 

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