39. Combination Sum

Given asetof candidate numbers (C)(without duplicates)and a target number (T), find all unique combinations inCwhere the candidate numbers sums toT.

Thesamerepeated number may be chosen fromCunlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set[2, 3, 6, 7]and target7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

Analysis:

DFS.

At each recursion, we loop from current position to end of array. subtract element if target is not less than that, then go to the next level.

Base case: when target == 0

Complexity:

Time: ?

Space: ?

Code:

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> returnList = new ArrayList<List<Integer>>();
        if(candidates == null || candidates.length == 0){
            return returnList;
        }

        dfs(target, 0, candidates, returnList, new ArrayList<Integer>());
        return returnList;
    }

    private void dfs(int target, int pos, int[] nums, List<List<Integer>> returnList, List<Integer> tempList){
        if(target == 0){
            returnList.add(new ArrayList<Integer>(tempList));
            return;
        }

        for(int i = pos; i < nums.length; i++){
            if(target >= nums[i]){
                tempList.add(nums[i]);
                dfs(target - nums[i], i, nums, returnList, tempList);
                tempList.remove(tempList.size()-1);
            }
        }
    }
}