LeetCode - Medium - 40. Combination Sum II

小灰灰 2023-01-05 12:57 139阅读 0赞

## Topic ##

*  Array
 *  Backtracking

## Description ##

[https://leetcode.com/problems/combination-sum-ii/][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 ##

[回溯算法：求组合总和（三）][Link 1]

## 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)));
    	}
    }

[https_leetcode.com_problems_combination-sum-ii]: https://leetcode.com/problems/combination-sum-ii/
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247485360&idx=1&sn=2256a0f01a304d82a2b59252327f3edb&scene=21#wechat_redirect