LintCode 135 Combination Sum

思路

与subsets的思路几乎一致，只是在递归出口条件和dfs的输入参数有一点不同。本题需要额外对输入数组进行去重，思路参考LintCode 521的思路（双指针去重）;也可以直接在dfs里面去重，当[i] == [i-1]时跳过即可。
。

复杂度

时间复杂度O(2^n)
空间复杂度O(logn)

代码

public class Solution {
    /*** @param candidates: A list of integers* @param target: An integer* @return: A list of lists of integers*/public List<List<Integer>> combinationSum(int[] candidates, int target) {
    // write your code hereList<List<Integer>> results = new ArrayList<>();if (candidates == null) {
    return results;}Arrays.sort(candidates);candidates = removeDup(candidates);dfs(candidates, 0, target, new ArrayList<>(), results);return results;}private void dfs(int[] candidates, int startIndex,int target,List<Integer> combination,List<List<Integer>> results) {
    if (target < 0) {
    return;}if (target == 0) {
    results.add(new ArrayList<>(combination));return;}for (int i = startIndex; i < candidates.length; i++) {
    combination.add(candidates[i]);dfs(candidates, i, target - candidates[i], combination, results);combination.remove(combination.size() - 1);}}private int[] removeDup(int[] nums) {
    // two pointersint index = 0;for (int i = 0; i < nums.length; i++) {
    if (nums[i] != nums[index]) {
    nums[++index] = nums[i];}}int[] result = new int[index + 1];for (int i = 0; i < index + 1; i++) {
    result[i] = nums[i];}return result;}
}

去重思路2： 直接在dfs里面去重，当[i] == [i-1]时跳过即可。

public class Solution {
    /*** @param candidates: A list of integers* @param target: An integer* @return: A list of lists of integers*/public List<List<Integer>> combinationSum(int[] candidates, int target) {
    // write your code hereList<List<Integer>> results = new ArrayList<>();if (candidates == null) {
    return results;}Arrays.sort(candidates);dfs(candidates, 0, target, new ArrayList<>(), results);return results;}private void dfs(int[] nums, int startIndex,int target,List<Integer> combination,List<List<Integer>> results) {
    if (target == 0) {
    results.add(new ArrayList<>(combination));return;}if (target < 0) {
    return;}for (int i = startIndex; i < nums.length; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) {
    continue;}combination.add(nums[i]);dfs(nums, i, target - nums[i], combination, results);combination.remove(combination.size() - 1);}}
}