Combination Sum

Question:

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

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

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

解法代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        backTrack(list, new ArrayList<Integer>(), candidates, target, 0);
        
        return list;
    }
    
    public void backTrack(List<List<Integer>> list, 
            List<Integer> listInt, int[] nums, int target, int start) {
        if(target == 0) {
            // 添加找到的解，一定要深拷贝一个对象保存到list中
            // 因为求解过程中始终用的listInt对象
            list.add(new ArrayList<Integer>(listInt));
            return;
        }
        for(int i = start; i < nums.length; i++) {
            // 由于数组是有序的
            // target - nums[i] < 0 后续的循环递归不可能找到解
            if(target - nums[i] < 0) {
                break;
            }
            listInt.add(nums[i]);
            // 递归调用的最后一个参数应该是i，而不是start
            // 如果是start则重复运算并且会出现重复解
            backTrack(list, listInt, nums, target - nums[i], i);
            // 回退一个位置继续求解
            listInt.remove(listInt.size() - 1);
        }
    }
}

测试代码

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

import com.kay.pro.alog.LeetCode39;

@RunWith(Parameterized.class)
public class LeetCode39Test {
    private LeetCode39 leetCode;
    private int[] nums;
    private int target;
    private List<List<Integer>> ret;
    
    public LeetCode39Test(int[] nums, int target, List<List<Integer>> ret) {
        this.nums = nums;
        this.target = target;
        this.ret = ret;
    }
    
    @Before
    public void before() {
        leetCode = new LeetCode39();
    }
    
    @Parameters
    public static Collection<?> reverserArrays() {
        List<List<Integer>> list1 = new ArrayList<List<Integer>>();
        list1.add(Arrays.asList(2, 2, 3));
        list1.add(Arrays.asList(7));
        
        List<List<Integer>> list2 = new ArrayList<List<Integer>>();
        list2.add(Arrays.asList(2, 2, 2, 2));
        list2.add(Arrays.asList(2, 3, 3));
        list2.add(Arrays.asList(3, 5));
        
        return Arrays.asList(new Object[][]{
            {new int[]{2,3,6,7}, 7, list1},
            {new int[]{2,3,5}, 8, list2}
        });
    }
    
    @Test
    public void leetCode33() {
        assertEquals(ret, leetCode.combinationSum(nums, target));
    }
}

Output：

Time And Space Complexity

Time: 二分查找时间复杂度
Space: 不需要使用额外的存储空间，原地替换

Tips

回溯法