给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
链接：https://leetcode-cn.com/problems/combination-sum-ii
List<List<Integer>> ans =new ArrayList<>();
ArrayList<int[]> freq=new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
for(int i=0;i<candidates.length;i++)
{
int size=freq.size();
if(size==0|| freq.get(size - 1)[0]!=candidates[i])
{
freq.add(new int[]{candidates[i],1});
}else {
freq.get(size-1)[1]++;
}
}
dfs(0,target,new ArrayList<Integer>());
return ans;
}
public void dfs(int index,int target,ArrayList<Integer> combin){
if(target==0)
{
ans.add(new ArrayList<Integer>(combin));
return;
}
if(index==freq.size()||target<freq.get(index)[0]) {
return;
}
//不选当前
dfs(index+1,target,combin);
//选择
int most=Math.min(target/freq.get(index)[0],freq.get(index)[1]);
// System.out.println(most);
// int most=freq.get(index)[1];
for(int i=0;i<most;i++) {
combin.add(freq.get(index)[0]);
dfs(index+1,target-(i+1)*freq.get(index)[0],combin);
}
for(int i=0;i<most;i++) {
combin.remove(combin.size() - 1);
}
}
public static void main(String[] args) {
System.out.println(new seqecStack().combinationSum2(new int[]{10,1,2,7,6,1,5},8));
}