Tuesday, January 28, 2014

LeetCode : Combination

public class Solution {
   
    public void reorg(int [] p, int x, int k)
    {
        int c=p[x]+1;
        for(int i=x+1;i<k;i++,c++)
           p[i]=c;
        return;
    }
   
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
       int p[]=new int[k];
       p[0]=1;
       reorg(p,0,k);
       int bound=n-k+2;
     
       ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();
     
       int kk=k-1;
       while(p[0]<bound&&kk>=0)
       {
           ArrayList<Integer> al=new ArrayList<Integer>();
           for(int i=0;i<k;i++)
             al.add(i,p[i]);
           all.add(al);
         
           kk=k-1;
           boolean reorgflag=false;
           while(kk>=0)
           {
               p[kk]++;

               if(reorgflag){
                   reorg(p,kk,k);
                   reorgflag=false;
               }
                       
               if(p[kk]>n-k+1+kk)
               {
                   kk--;
                   reorgflag=true;
               }
               else break;
           }
       }

        return all;
    }
}

No comments:

Post a Comment