Recursive +DP(Memoization) Java solution


  • 0
    H
    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            if(n==0) return new LinkedList();
            List<List<Integer>>[][] result=new LinkedList[k+1][n+1];
            helper(result,n,k,1,new LinkedList());
            return result[k][1];
        }
        public List<List<Integer>> helper(List<List<Integer>>[][] result,int n,int k,int start,List<Integer> temp){
            if(k==0||start>n) {List<List<Integer>> res=new LinkedList(); res.add(new LinkedList()); return res;}
            if(result[k][start]!=null) return result[k][start];
            else{
                List<List<Integer>> res=new LinkedList();
                for(int i=start;i<=n;i++){
                    List<List<Integer>> ls=helper(result,n,k-1,i+1,temp);
                    for(List<Integer> l:ls){
                        if(l.size()==k-1){
                            List<Integer> tmp=new LinkedList(temp);
                            tmp.add(i);
                            tmp.addAll(l);
                            res.add(tmp);
                        }
                    }
                }
                if(result[k][start]==null) result[k][start]=new LinkedList(res);
                return res;
            }
        }
    }
    

Log in to reply
 

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