A java DP solution using a 3D array


  • 1
    A

    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) {
    		ret.add(path);
    		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>();
    			clone.addAll(path);
    			clone.add(0,i);
    			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));
    }
    

    }


Log in to reply
 

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