1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

/*
 * @lc app=leetcode id=40 lang=java
 *
 * [40] Combination Sum II
 *
 * https://leetcode.com/problems/combination-sum-ii/description/
 *
 * algorithms
 * Medium (53.88%)
 * Likes:    9859
 * Dislikes: 261
 * Total Accepted:    861.2K
 * Total Submissions: 1.6M
 * Testcase Example:  '[10,1,2,7,6,1,5]\n8'
 *
 * 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
 * 
 * 
 * 
 * 
 * solution:
 * 
 *   * @param candidates 候选数组
     * @param begin      从候选数组的 begin 位置开始搜索
     * @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
     * @param cur       从根结点到叶子结点的路径
     * @param combination 最终的所有组合

参考链接：https://leetcode.cn/problems/combination-sum-ii/solutions/14753/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
 * 
 * 深度优先搜素
 * 注意去重
 * 
 */

// @lc code=start

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

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> combination = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        if(candidates.length == 0){
            return combination;
        }
        Arrays.sort(candidates);
        dfs(candidates, target, 0, combination, cur);
        return combination;
    }

    public void dfs(int[] candidates, int target, int begin,List<List<Integer>> combination, List<Integer> cur){
        if(target==0){
            combination.add(new ArrayList<>(cur));
            return;
        }
        for(int i = begin; i< candidates.length;i++){
          //大剪枝，减去 target比candidates[i]小的
          if(target<candidates[i]){
            return;
          }
          //小剪枝，排序后，同一层，相同元素，会产生重复组合，所以进行跳过去重
          if(i>begin && candidates[i] == candidates[i-1] ){
            continue;
          }
          cur.add(candidates[i]);
          //注意元素不能重复使用，所以下一层搜索begin从i+1开始搜索
          dfs(candidates,target - candidates[i],i+1,combination,cur);
          cur.remove(cur.size() -1);
        }
    }
}
// @lc code=end