[LeetCode] 40. Combination Sum II

【原题】 Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

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目标相同,但是给定的候选集合中可能会有重复的元素,而再返回的集合当中要求不能重复。且同一个元素不能重复使用。 【思路】 主要的问题在于相同元素会导致结果当中有相同的集合,使用排序可以解决重复集合的问题。

public class Solution {
    public void combinationSumCore(List<List<Integer>> results, List<Integer> result,int[] candidates,int index,int target,int sum){
        if(sum==target) {
            results.add(new ArrayList<Integer>(result));
            return;
        }
        if(sum>target) return;
        for(int i=index;i<candidates.length;i++){
            if(i>index&&candidates[i]==candidates[i-1])//相同的元素跳过,用来避免同一子集多次加入到结果集合当中
             continue;
            result.add(candidates[i]);
            sum+=candidates[i];
            combinationSumCore(results, result,candidates,i+1,target,sum);//元素不能重复使用所以从下一个元素开始
            sum-=candidates[i];
            result.remove(result.size()-1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> results=new ArrayList<List<Integer>>();
        List<Integer> result=new ArrayList<>();
        Arrays.sort(candidates);//先排序
        combinationSumCore(results,result,candidates,0,target,0);
        return results;
    }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏郭耀华‘s Blog

剑指offer第五天

28.数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2...

2605
来自专栏HappenLee的技术杂谈

C++雾中风景6:拷贝构造函数与赋值函数

这里我们显式声明了拷贝构造函数与赋值构造函数,接下来我们用一小段代码测试一下上面定义的类。(其他函数的定义并不完整,读者可以之行补全)

562
来自专栏desperate633

LeetCode 1. Two Sum分析代码

利用hashmap存储每个元素的值和所在的下标,遍历一遍,如果target-nums[i]在map里直接取出index值返回就可以了。leetcode 的第一道...

932
来自专栏程序生活

Leetcode-Easy21. Merge Two Sorted ListsDefinition for singly-linked list.class ListNode:def init(sel

21. Merge Two Sorted Lists 描述: 将两个有序链表进行合并,合并之后的链表也是有序链表 ? 思路: 递归 代码 ...

2513
来自专栏技术碎碎念

LeetCode-1- Two Sum

Given an array of integers, return indices of the two numbers such that they add...

2768
来自专栏西安-晁州

golang学习之闭包

匿名函数不能够独立存在,但可以被赋值于某个变量,即保存函数的地址到变量中:fplus := func(x, y int) int { return x + y ...

1850
来自专栏书山有路勤为径

堆的基础知识

二叉堆是非线性的树形的数据结构,有两种堆,最大堆与最小堆。最大堆,树种各个父 节点的值总是大于或等于任何一个子节点的值;最小堆,树种各个父节点的值总是小于或 等...

653
来自专栏技术碎碎念

LeetCode-15-3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b ...

34911
来自专栏Bingo的深度学习杂货店

Q720 Longest Word in Dictionary

Given a list of strings words representing an English Dictionary, find the longe...

1033
来自专栏程序生活

Leetcode-Easy 437. Path Sum III

101. Symmetric Tree 描述: 给定一个二叉树和一个目标和,求满足和为目标值的路径个数 ? 思路: dfs 深度优先搜索 ...

3334

扫码关注云+社区