Java solution using recursive


  • 64
    L
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        	Arrays.sort(candidates);
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            getResult(result, new ArrayList<Integer>(), candidates, target, 0);
            
            return result;
        }
        
        private void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start){
        	if(target > 0){
        		for(int i = start; i < candidates.length && target >= candidates[i]; i++){
        			cur.add(candidates[i]);
        			getResult(result, cur, candidates, target - candidates[i], i);
        			cur.remove(cur.size() - 1);
        		}//for
        	}//if
        	else if(target == 0 ){
        		result.add(new ArrayList<Integer>(cur));
        	}//else if
        }
    }

  • 0
    H

    HI,There is a problem:when the input is [1,1],1 the output is [[1],[1]] .
    Maybe add the condition if(candidate[i]!=candidate[i-1]) in the loop
    can work!


  • 1
    J

    if (i > 0 && candidates[i] == candidates[i - 1])
    continue;


  • 0
    R
    This post is deleted!

  • 3
    E

    From large to small might be easier and shorter.

    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> result = new ArrayList<>();
            dfs(result, new LinkedList<Integer>(), candidates, target);
            return result;
        }
        private void dfs(List<List<Integer>> result, LinkedList<Integer> list, int[] arr, int target) {
            if (target == 0) {
                result.add(new LinkedList<Integer>(list));
                return;
            }
            for (int i = arr.length - 1; i >= 0; i--) {
                if (arr[i] <= target) {
                    list.addFirst(arr[i]);
                    dfs(result, list, Arrays.copyOfRange(arr, 0, i + 1), target - arr[i]);
                    list.removeFirst();
                }
            }
        }
    }

  • 1
    S

    Thanks for the answer! could someone help me understand why the cur.remove(...) is needed there? will it be guaranteed to be removing what's been added before the recursion call?


  • 0
    L

    Okay, thank your advice, I will add more comment in other answers.


  • 0
    M

    Nice and clear solution.


  • 1
    S

    hello, in your backtracing:
    getResult(result, cur, candidates, target - candidates[i], i);
    why the start is still i, but doesn't move to i+1?


  • 0
    L

    The problem allows the numbers in the list can use many times.


  • 1

    Nice solution ! The "remove" is needed because we cannot have a "0" element in the result list ( since target==0 is where the recursion starts to comes back ).


  • 1

    This solution allows this feature, because for any target we always start from the start.


  • 0
    D

    Nice Solution!


  • 0
    A

    I have a very basic question. Why it is "result.add(new ArrayList<Integer>(cur));" in the last line. Could it just be "result.add(cur)". But it gave me wrong answer.


  • 5
    S

    You can't write like this, because cur is an ArrayList which is an object, and cur is just the reference of this object, the content of this object will change every time. So if you just add cur, I guess it will return an ArrayList of the last cur


  • 0
    X

    I can't understand cur.remove(cur.size() - 1);,what does it mean?


  • 1
    Q

    Means deleting the element that was just added, that is called backtrack.


  • 0
    M

    What is the running time of this algorithm? O(n 2^n)? where n is the length of candidates


  • 0
    P

    Implicit assumption of the problem is, a set of candidate numbers does not have the duplications.


  • 7
    Y

    A little revise without using Arrays.sort which will run faster.

    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            combinationSum(result,new ArrayList<Integer>(),candidates,target,0);
            return result;
        }
        public void combinationSum(List<List<Integer>> result, List<Integer> cur, int[] candidates, int target,int start) {
            if (target > 0) {
                for (int i = start;i < candidates.length;i++) { // not using the condition "target >= candidates[i]"
                    cur.add(candidates[i]);
                    combinationSum(result, cur, candidates, target-candidates[i],i);
                    cur.remove(cur.size() - 1);
                }
            }
            if (target == 0) result.add(new ArrayList<Integer>(cur));
        }
    }
    

    I think we do not need to care about the order in the candidates. Please point out if I'm wrong.


Log in to reply
 

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