LeetCode - Medium - 40. Combination Sum II-蒲公英云

Topic

Array
Backtracking

Description

https://leetcode.com/problems/combination-sum-ii/

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

Analysis

回溯算法：求组合总和（三）

Submission

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class CombinationSumII { 
    // 版本一：公众号“代码随想录”的
    public List<List<Integer>> combinationSum2(int[] candidates, int target) { 
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backtracking(path, candidates, target, used, 0, 0, result);
        return result;
    }
    private void backtracking(List<Integer> path, int[] candidates, int target, //
            boolean[] used, int sum, int startIndex, List<List<Integer>> result) { 
        if (target == sum) { 
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) { 
            if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == false)
                continue;
            sum += candidates[i];
            path.add(candidates[i]);
            used[i] = true;
            backtracking(path, candidates, target, used, sum, i + 1, result);
            sum -= candidates[i];
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
    // 版本二，跟版本一相比，没有sum，used变量
    public List<List<Integer>> combinationSum2_(int[] candidates, int target) { 
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        Arrays.sort(candidates);
        backtracking_(candidates, 0, target, path, res);
        return res;
    }
    private void backtracking_(int[] candidates, int startIndex, int target, List<Integer> path,
            List<List<Integer>> res) { 
        if (target == 0) { 
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length && target >= candidates[i]; i++) { 
            if (i > startIndex && candidates[i] == candidates[i - 1])
                continue;
            path.add(candidates[i]);
            backtracking_(candidates, i + 1, target - candidates[i], path, res);
            path.remove(path.size() - 1);
        }
    }
    // 版本三，将版本一的used剔除掉，以及backtracking__方法体的 `i > 0 &&` 改为 `i > startIndex &&`
    public List<List<Integer>> combinationSum2__(int[] candidates, int target) { 
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking__(path, candidates, target, 0, 0, result);
        return result;
    }
    private void backtracking__(List<Integer> path, int[] candidates, int target, //
            int sum, int startIndex, List<List<Integer>> result) { 
        if (target == sum) { 
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) { 
            if (i > startIndex && candidates[i - 1] == candidates[i])
                continue;
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking__(path, candidates, target, sum, i + 1, result);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

Test

import static org.junit.Assert.*;
import java.util.Arrays;
import org.hamcrest.collection.IsIterableContainingInAnyOrder;
import org.junit.Test;
public class CombinationSumIITest { 
    @Test
    @SuppressWarnings("unchecked")
    public void test() { 
        CombinationSumII obj = new CombinationSumII();
        assertThat(obj.combinationSum2(new int[] {  10, 1, 2, 7, 6, 1, 5 }, 8), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(1, 1, 6), Arrays.asList(1, 2, 5), //
                        Arrays.asList(1, 7), Arrays.asList(2, 6)));
        assertThat(obj.combinationSum2(new int[] {  2, 5, 2, 1, 2 }, 5), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(1, 2, 2), Arrays.asList(5)));
    }
    @Test
    @SuppressWarnings("unchecked")
    public void test2() { 
        CombinationSumII obj = new CombinationSumII();
        assertThat(obj.combinationSum2_(new int[] {  10, 1, 2, 7, 6, 1, 5 }, 8), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(1, 1, 6), Arrays.asList(1, 2, 5), //
                        Arrays.asList(1, 7), Arrays.asList(2, 6)));
        assertThat(obj.combinationSum2_(new int[] {  2, 5, 2, 1, 2 }, 5), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(1, 2, 2), Arrays.asList(5)));
        assertThat(obj.combinationSum2_(new int[] {  1, 1, 1}, 3), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(1, 1, 1)));
    }
    @Test
    @SuppressWarnings("unchecked")
    public void test3() { 
        CombinationSumII obj = new CombinationSumII();
        assertThat(obj.combinationSum2__(new int[] {  10, 1, 2, 7, 6, 1, 5 }, 8), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(1, 1, 6), Arrays.asList(1, 2, 5), //
                        Arrays.asList(1, 7), Arrays.asList(2, 6)));
        assertThat(obj.combinationSum2__(new int[] {  2, 5, 2, 1, 2 }, 5), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(1, 2, 2), Arrays.asList(5)));
        assertThat(obj.combinationSum2__(new int[] {  1, 1, 1}, 3), //
                IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(1, 1, 1)));
    }
}