Share my 11-line java solution with simple comments


  • 0
    M
    public class Solution {
        public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> ans = new ArrayList<>();
            dfs(ans, new ArrayList<Integer>(), n, 0, n, k);
            return ans;
        }
        
        private void dfs(List<List<Integer>> ans, List<Integer> list, int n, int prev, int valLeft, int cntLeft) {
            if (valLeft==0 && cntLeft==0) { ans.add(new ArrayList<Integer>(list)); return; }  // valLeft==0&&cntLeft==0, collect current answer
            if (valLeft>0 && cntLeft>0) { // can proceed
                for (int i=prev+1; i<=Math.min(n, 9); ++i) {  // begin with prev+1 
                    list.add(i);
                    dfs(ans, list, n, i, valLeft-i, cntLeft-1);
                    list.remove(list.size()-1);
                }
            }
        }
    }

Log in to reply
 

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