JAVA simple backtrack solution 1ms


  • 0
    H

    Hello guys, the combination sum series problems are traditional backtracking problems, just like the N-queens,they are worth to try and you'll figure out the concept of backtracking.

    Fight for interviews!

    public List<List<Integer>> combinationSum3(int k, int n) {
    	List<List<Integer>> list = new ArrayList<>();
    	backtrack(list, new ArrayList<Integer>(), k, n, 1);
    	return list;
    }
    private static void backtrack(List<List<Integer>> list, ArrayList<Integer> temp, int k, int sum, int start) {
    	if (sum < 0) {
    		return;
    	} else if (temp.size() == k && sum == 0) {
    		list.add(new ArrayList<Integer>(temp));
    	} else {
    		for (int i = start; i <= 9; i++) {
    			temp.add(i);
    			backtrack(list, temp, k, sum - i, i + 1);
    			temp.remove(temp.size() - 1);
    		}
    	}
    }

Log in to reply
 

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