# A java DP solution using a 3D array

• create a boolean 3D array to store all the subproblems. i, j and k, i is the sum, j is the subarray ending at j and k is the length of the subarray.
given this model, matrix[i][j][k] is true means there exists a combinational sum i with given constraints specified by j and K. matrix[i][j][k] = matrix[i-j][1][k - 1] ||… matrix[i-j][j-1][k-1].

The time complexity for this algorithm is O(81kn). Then we can traverse the matrix to find all the different combinations.

I think there should be a way to reduce the time complexity to O(9kn) as the most inner loop is not necessary. Haven't figured how yet.

``````public class CombinationSum3 {
public List<List<Integer>> combinationSum3(int k, int n) {
int x = n + 1;
int y = 10;
int z = k + 1;
boolean[][][] partialSol = new boolean[x][y][z];
partialSol[0][0][0] = true;
for (int i = 1; i < x; i++) {
for (int j = 1; j < y; j++) {
for (int s = 1; s < z; s++) {
partialSol[i][j][s] = false;
for (int r = j - 1; r >= 0; r--) {
if (i - j >= 0 && s - 1 >= 0)
partialSol[i][j][s] = partialSol[i][j][s] || partialSol[i - j][r][s - 1];
}
}
}
}
List<List<Integer>> ret = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<Integer>();
traversematrix(ret, partialSol, path, k, n);
return ret;
}

public void traversematrix(List<List<Integer>> ret, boolean[][][] matrix, List<Integer> path, int k, int n) {
if (k == 0 && n == 0) {
return;
}
if (k == 0 || n == 0) {
return;
}
int end = 10;
if (!path.isEmpty()) {
end = path.get(0);
}
for (int i = 1; i < end; i++) {
if (n - i >= 0 && k - 1 >= 0 && matrix[n][i][k]) {
ArrayList<Integer> clone = new ArrayList<Integer>();
traversematrix(ret, matrix, clone, k - 1, n - i);
}
}
}
public static void main(String[] args){
CombinationSum3 sol = new CombinationSum3();
System.out.println(sol.combinationSum3(3, 9));
}
``````

}

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