My solutions for using recursion and DP


  • 0
    A
    /* recurisve solution*/
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for(int i = 1; i <= n-k+1; i++)
        {
            ArrayList<Integer> path = new ArrayList<Integer>();
            path.add(i);
            helper(path, k-1, n, res);
        }
        return res;
    }
    
    public void helper(List<Integer> line, int cnt, int n, List<List<Integer>> res)
    {
       if(cnt == 0)
       {
           res.add(line);
           return;
       }
       int last = line.get(line.size()-1);
       for (int i = last+1; i <= n-cnt+1; i++)
       {
           ArrayList<Integer> path = new ArrayList<Integer>();
           path.addAll(line);
           path.add(i);
           helper(path, cnt-1, n, res);
       }
    }
    
    
    /*dp solution*/
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        // initialize
        for (int i = 1; i <= n-k+1; i++)
        {
            List<Integer> line = new ArrayList<Integer>();
            line.add(i);
            res.add(line);
        }
        
        // from (n-1, m-1) ==> (n, m)
        for (int i = 1; i < k; i++)
        {
            int j = 0;
            int length = res.size();
            while(j < length)
            {
                List<Integer> l = res.get(j);
                int last = l.get(l.size()-1);
                boolean firstRun = true;
                for (int m = last + 1; m <= n- (k-i)+1; m++)
                {
                    //change l and spawn new elements
                    if(firstRun)
                    {
                        l.add(m);
                        firstRun = false;
                    }
                    else
                    {
                        List<Integer> newspawn = new ArrayList<Integer>();
                        newspawn.addAll(l.subList(0,l.size()-1));
                        newspawn.add(m);
                        res.add(newspawn);
                    }
                }
                j++;
            }
        }
        return res;
    }

Log in to reply
 

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