7ms Java solution using backtracking

  • 0

    similar problems:
    Combination Sum
    Combination Sum II
    Combination Sum III
    Combination Sum IV
    These problems can be solved with similar code.

    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(candidates.length == 0){
                return res;
            compute(candidates, target, 0, 0, new ArrayList<Integer>(), res);
            return res;
        public void compute(int[] candidates, int target, int sum, int start, List<Integer> list, List<List<Integer>> res){
            if(sum == target){
                res.add(new ArrayList<Integer>(list));
            }else if(sum > target){
                for(int index = start; index < candidates.length; index++){
                    if(sum + candidates[index] <= target){
                        sum = sum + candidates[index];
                        compute(candidates, target, sum, index, list, res);
                        list.remove(list.size() - 1);
                        sum = sum - candidates[index];

Log in to reply

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