【leetcodeブラシノート】Combination Sum II
5254 ワード
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums toT.
Each number in C may only be used once in the combination.
Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). The solution set must not contain duplicate combinations.
For example, given candidate set
Combination Sumとの違いは上の赤い行で、再帰時の起点をiからi+1に変更すれば、以下のコードでハイライトされている部分を参照してください.
コードは次のとおりです.
Each number in C may only be used once in the combination.
Note:
For example, given candidate set
10,1,2,7,6,1,5
and target 8
, A solution set is: [1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
Combination Sumとの違いは上の赤い行で、再帰時の起点をiからi+1に変更すれば、以下のコードでハイライトされている部分を参照してください.
コードは次のとおりです.
1 public class Solution {
2 private void combiDfs(int[] candidates,int target,List<List<Integer>> answer,List<Integer> numbers,int start){
3 if(target == 0){
4 answer.add(new ArrayList<Integer>(numbers));
5 return;
6 }
7
8 int prev = -1;
9
10 for(int i = start;i < candidates.length;i++){
11 if(candidates[i] > target)
12 break;
13 if(prev != -1 && prev == candidates[i])
14 continue;
15
16 numbers.add(candidates[i]);
17 combiDfs(candidates, target-candidates[i], answer, numbers,i+1); 18 numbers.remove(numbers.size()-1);
19
20 prev = candidates[i];
21 }
22 }
23 public List<List<Integer>> combinationSum2(int[] candidates, int target) {
24 List<List<Integer>> answer = new ArrayList<List<Integer>>();
25 List<Integer> numbers = new ArrayList<Integer>();
26 Arrays.sort(candidates);
27 combiDfs(candidates, target, answer, numbers,0);
28
29 return answer;
30
31 }
32 }