Combination Sum 组合数求和-Leetcode

原题:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

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 2,3,6,7 and target 7,  A solution set is:  [7] [2, 2, 3]


题意是找到所有加起来和为target值的组合,候选数可以重复使用。这明显是一道利用回溯的题目,可以想象成深度搜索。

以题目给出的【2,3,6,7】为例。一棵树根节点有四个子节点(2,3,6,7)。每个子节点下又有不小于本子节点的所有子节点。比如子节点2下面仍然有(2,3,6,7)四个子节点,子节点3下面有(3,6,7)三个子节点。我们就在这样一棵树上进行深搜,返回的条件是经过的节点的和为target。停止的条件是返回到根节点且无下一个子节点可用。

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        solve(candidates,0,target,new LinkedList<Integer>());
        return ans;
    }
    private List<List<Integer>> ans=new LinkedList<>();
    private  void solve(int[] candidates,int start,int target,LinkedList<Integer> current){
        if (target==0){
            ans.add(copy(current));
            return;
        }
        if (target<candidates[start]){
            return;
        }
        else {
            for (int iterator=start;iterator<candidates.length;iterator++){
                if (candidates[iterator]>target){
                    break;
                }
                current.add(candidates[iterator]);
                solve(candidates, iterator, target - candidates[iterator], current);
                current.pollLast();
            }
            return;
        }
    }
    private LinkedList<Integer> copy(LinkedList<Integer> source){
        LinkedList<Integer> dest=new LinkedList<>();
        for (int i:source){
            dest.add(i);
        }
        return dest;
    }
}

另一个效率更高的算法,逆向思维。

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        return combinationSum(candidates, target, 0);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target, int start) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] <target) {
                for (List<Integer> ar : combinationSum(candidates, target - candidates[i], i)) {
                    ar.add(0, candidates[i]);
                    res.add(ar);
                }
            } else if (candidates[i] == target) {
                List<Integer> lst = new ArrayList<>();
                lst.add(candidates[i]);
                res.add(lst);
            } else
                break;
        }
        return res;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WD学习记录

Python数据结构与算法笔记(4)

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

13120
来自专栏nnngu

数据结构08 线索二叉树

上一篇总结了二叉树,这一篇要总结的是线索二叉树,我想从以下几个方面进行总结。 1、什么是线索二叉树? 2、为什么要建立线索二叉树? 3、如何将二叉树线索化? 4...

35560
来自专栏java学习

来测试一下你对数据结构中的栈和队列的了解有多少?

选择题 1.向一个栈顶指针为top的链栈中插入一个结点s,执行( )。 A.top.next=s; B.s.next=top.next ;top.next=s;...

65090
来自专栏尾尾部落

[剑指offer] 二叉树的镜像

通过对以上两棵树的观察,我们可以总结出这两棵树的根节点相同,但它们的左、右两个子节点交换了位置。所以我们可以得出求一棵树的镜像的过程:先前序遍历这棵树的每个节点...

16820
来自专栏猿人谷

线性表简介

学习数据结构 -> 线性表 -> 线性表的介绍     线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中...

22080
来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

19420
来自专栏ACM算法日常

算法合集 | 神奇的笛卡尔树 - HDU 1506

笛卡尔树是一个很有意思的树形结构,因为它同时满足两个性质,从key(key就是索引位置,如下图中9的key为1,3的key为2......)来看...

43320
来自专栏技术专栏

无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

56820
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

544100
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

17620

扫码关注云+社区

领取腾讯云代金券