Simple Java backtracking solution


  • 0
    R

    The path should be length k since we are picking k number from n.

    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res = new ArrayList<List<Integer>> ();
            dfs(n,0,k,new ArrayList(),res);
            return res;
        }
        
        private void dfs(int n,int index,int k,List<Integer> path,List<List<Integer>> res){
            if(path.size()==k){
                res.add(new ArrayList(path));//not add path to result until path length match k
                return;
            }
            for(int i=index;i<n;i++){
                path.add(i+1);
                dfs(n,i+1,k,path,res);
                path.remove(path.size()-1);
            }
        }
    }
    

Log in to reply
 

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