# Java DP solution with complement trick

• 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>();
}
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>();
}
}
}
}
}
}

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++;}
}
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);
}
return output;
}

public static List<List<Integer>> combinationSum3(int k, int n) {
if (k==9 && n==45) {
ArrayList<Integer> Alpha=new ArrayList<Integer>();
ArrayList<List<Integer>> out=new ArrayList<List<Integer>>();
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;
}
``````

}

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