Java DP solution with complement trick


  • 0
    T

    public class Solution {
    static class Node {
    //every List<Integer> in A is always sorted
    List<List<Integer>> A;

        public Node(){
            this.A=new ArrayList<List<Integer>>();
        }
    }
    
    public static boolean noK(List<Integer> A,int k){
    	for (int i=0;i<A.size();i++){
    		if (A.get(i)==k) return false;
    	}
    	return true;
    }
    
    public static void fillGrid(Node[][] D,int i,int j){
    	for (int k=1;k<10;k++){
    		//depend on grid D[i-1][j-k]
    		if (j-k>=0){
    			//if that is init grid
    			if (j-k==0 && i==1 && D[i-1][j-k].A.size()==0){
    				ArrayList<Integer> p=new ArrayList<Integer>();
    				p.add(k);
    				D[i][j].A.add(p);
    			}
    			else {
    				//for each ArrayList in D[i-1][j-k],
    				for (List<Integer> p:D[i-1][j-k].A){
    					//add elements that does not contain element k
    					if (p.get(p.size()-1)<k) {
    						ArrayList<Integer> p2=new ArrayList<Integer>();
    						p2.addAll(p);p2.add(k);
    						D[i][j].A.add(p2);
    					}
    				}
    			}
    		}
    	}
    }
    
    public static ArrayList<Integer> compleList(List<Integer> in){
    	int index=0;
    	ArrayList<Integer> output=new ArrayList<Integer>();
    	for (int k=1;k<10;k++){
    		if (k==in.get(index)) {if (index<in.size()-1) index++;}
    		else {output.add(k);}
    	}
    	return output;
    }
    
    public static List<List<Integer>> complement(List<List<Integer>> Alpha){
    	List<List<Integer>> output=new ArrayList<List<Integer>>();
    	for (List<Integer> beta:Alpha){
    		ArrayList<Integer> outBeta=compleList(beta);
    		output.add(outBeta);
    	}
    	return output;
    }
    
    public static List<List<Integer>> combinationSum3(int k, int n) {
        if (k==9 && n==45) {
    		ArrayList<Integer> Alpha=new ArrayList<Integer>();
    		Alpha.add(1);Alpha.add(2);Alpha.add(3);Alpha.add(4);Alpha.add(5);
    		Alpha.add(6);Alpha.add(7);Alpha.add(8);Alpha.add(9);
    		ArrayList<List<Integer>> out=new ArrayList<List<Integer>>();
    		out.add(Alpha);
    		return out;}
    	if (k>=5) return complement(combinationSum3(9-k,45-n));
        //D[i][j] stand for using i numbers to get j
    	Node[][] D=new Node[k+1][n+1];
    	//init & init boundary
    	for (int i=0;i<=k;i++){
    		for (int j=0;j<=n;j++){
    			D[i][j]=new Node();
    		}
    	}
    	//recur
    	for (int i=1;i<=k;i++){
    		for (int j=1;j<=n;j++){
    			fillGrid(D,i,j);
    		}
    	}
    	for (List<Integer> L:D[k][n].A){
    		Collections.sort(L);
    	}
    	
    	return D[k][n].A;
    }
    

    }


Log in to reply
 

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