加起来和为目标值的组合

题目描述

给出一组候选数\ C C 和一个目标数\ T T，找出候选数中起来和等于\ T T 的所有组合。
\ C C 中的每个数字在一个组合中只能使用一次。

注意：

• 题目中所有的数字（包括目标数\ T T ）都是正整数
• 组合中的数字 (a_1, a_2, … , a_ka1,a2,…,a**k) 要按非递增排序 (a_1 \leq a_2 \leq … \leq a_ka1≤a2≤…≤a**k).
• 结果中不能包含重复的组合
• 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

示例1

输入

复制

[100,10,20,70,60,10,50],80

返回值

复制

[[10,10,60],[10,20,50],[10,70],[20,60]]

说明

给定的候选数集是[100,10,20,70,60,10,50]，目标数是80  

回溯

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] nums, int target) {
        this.target = target;
        ArrayList<Integer> list = new ArrayList<>();
        // 这里排序很重要
        Arrays.sort(nums);
        dfs(nums,0,0,list);
        return res;
    }
    int target = 0;
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public void dfs(int []nums,int index,int sum,ArrayList<Integer> list){
        if(index > nums.length||sum>target)return;
        if(sum == target){
            if(!res.contains(list)){
                res.add(new ArrayList(list));
            }
            return;
        }
        // 回溯
        for(int i=index;i<nums.length;i++){
            list.add(nums[i]);
            dfs(nums,i+1,sum+nums[i],list);
            list.remove(list.size()-1);
        }
    }
}

赏

谢谢你请我吃糖果

微信