Java实现LeetCode(组合总和)

leetcode题目

组合总和 -- leetcode 39

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ,

找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。

解集不能包含重复的组合。 

示例 1:

输入: candidates = [2,3,6,7], target = 7,

所求解集为:

[

  [7],

  [2,2,3]

]

示例 2:

输入: candidates = [2,3,5], target = 8,

所求解集为:

[

  [2,2,2,2],

  [2,3,3],

  [3,5]

]

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/combination-sum

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

回溯算法

递归找和为target的组合,出口为和超过了target

代码

package com.leetcode.array;

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

/**
 * 题目:
 * 组合总和 -- leetcode 39
 *
 * 题目描述:
 *
给定一个无重复元素的数组 candidates 和一个目标数 target ,
找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。 

示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
 */
public class CombinationSum {
	/**
	 * 思路:
	 * 1、回溯算法
	 * 2、递归找和为target的组合,出口为和超过了target
	 */
    public List<List<Integer>> combinationSum(int[] bb, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (bb == null) {
            return res;
        }

        addCombinations(bb, 0, target, new ArrayList<Integer>(), res);

        return res;
    }

    private void addCombinations(int[] bb, int start, int target, List<Integer> cache, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(cache));
            return;
        }
        for (int i=start; i<bb.length; i++) {
            cache.add(bb[i]);
            addCombinations(bb,i,target-bb[i],cache,res);
            cache.remove(cache.size()-1);
        }
    }

    /**
     * 思路:
     * 优化后的回溯
     */
    public List<List<Integer>> combinationSumII(int[] bb, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (bb == null) {
            return res;
        }

        // 排序数组后 可以在递归的时候减少递归次数,配合 if (bb[i] > target) break;
        Arrays.sort(bb);

        addCombinationsII(bb, 0, target, new ArrayList<Integer>(), res);

        return res;
    }

    private void addCombinationsII(int[] bb, int start, int target, List<Integer> cache, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(cache));
            return;
        }
        for (int i=start; i<bb.length; i++) {
        	// 配合排序后的数组 提升性能
            if (bb[i] > target) {
                break;
            }
            cache.add(bb[i]);
            addCombinationsII(bb,i,target-bb[i],cache,res);
            cache.remove(cache.size()-1);
        }
    }
}

到此这篇关于Java实现LeetCode(组合总和)的文章就介绍到这了,更多相关Java实现组合总数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java实现LeetCode(两数之和)

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • 如何用C++制作LeetCode刷题小技巧-错题记录本

    一 . 刷题小技巧 1,c++中的for(auto a:b)用法 for(auto a:b)中b为一个容器,效果是利用a遍历并获得b容器中的每一个值,但是a无法影响到b容器中的元素. for(auto &a:b)中加了引用符号,可以对容器中的内容进行赋值,即可通过对a赋值来做到容器b的内容填充. 2,c++中map的元素进行按照值排序(默认按照键排序) 为什么不能对map进行按值排序呢?因为sort排序只能对线性结构进行排序,而map是采用红黑树的数据结构. 一是通过将map转换到序列容器,再用

  • Java实现LeetCode(螺旋矩阵)

    LeetCode54. 螺旋矩阵 java实现 题目 难度 中 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入:  [   [ 1, 2, 3 ],   [ 4, 5, 6 ],   [ 7, 8, 9 ]  ]  输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入:  [    [1, 2, 3, 4],    [5, 6, 7, 8],    [9,10,11,12]  ] 输出: [1,2,3,4,8

  • vscode刷acm、leetcode的题目

    目录 简介 编译器 Windows 使用 Code Runner 插件运行代码 使用 C/C++ 插件编译并调试 安装插件 配置编译 配置 GDB/LLDB 调试器 开始调试代码 简介 Visual Studio Code(以下简称 VS Code) 是一个由微软开发,同时支持 Windows.Linux 和 macOS 等操作系统且开放源代码的代码编辑器.它是用 TypeScript 编写的,并且采用 Electron 架构.它带有对 JavaScript.TypeScript 和 Node.

  • Java实现LeetCode(报数)

    题目如下: public String countAndSay(int n) { if(n == 1){ return "1"; } //递归调用,然后对字符串处理 String str = countAndSay(n-1) + "*";//为了str末尾的标记,方便循环读数 char[] c = str.toCharArray(); int count = 1; StringBuilder s = new StringBuilder(); for(int i =

  • Java实现LeetCode(组合总和)

    leetcode题目 组合总和 -- leetcode 39 题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的数字可以无限制重复被选取. 说明: 所有数字(包括 target)都是正整数. 解集不能包含重复的组合.  示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [   [7],   [2,2,3

  • JAVA设计模式之组合模式原理与用法详解

    本文实例讲述了JAVA设计模式之组合模式.分享给大家供大家参考,具体如下: 组合(整体与部分关系)模式:将不同但是相关的对象组合成树形结构以实现"部分-整体"的层次结构,使得用户对单个对象和组合对象的使用具有一致性. * 模式角色组成: 1.Component对象: 是组合中的对象接口,是所有类共有的接口.是用于统一定义整体中的部分. 2.Leaf对象: 整体中的部分,没有下一级. 3.Composite对象: 用来存储子部件,在Component接口中实现与部分有关操作. 以公司构成

  • java实现Composite组合模式的实例代码

    //20210121 写在前面:刚期末考试完,考了面向对象,里边儿有23个设计模式,我寻思着考完挨个儿实现一下,本文实现组合模式 组合模式核心思想类似文件夹的概念,构件树形结构,树形有叶子结点和文件夹结点,文件夹结点可以包含叶子结点和文件夹结点 分为两种模式 - 透明型:所有节点构造全部相同,但是由于叶子结点没有下层结点,所以其有些方法为空,会不安全 - 安全型:叶子结点和文件架节点构造不同,这样展示的时候需要判断节点属性,不方便调用,但是由于没有空方法,会很安全 透明型组合模式程序源代码: /

  • 如何用Java实现排列组合算法

    需求 我们的数据表有多个维度,任意多个维度组合后进行 group by 可能会产生一些"奇妙"的反应,由于不确定怎么组合,就需要将所有的组合都列出来进行尝试. 抽象一下就是从一个集合中取出任意元素,形成唯一的组合.如[a,b,c]可组合为[a].[b].[c].[ab].[bc].[ac].[abc]. 要求如下: 组合内的元素数大于 0 小于等于 数组大小: 组合内不能有重复元素,如 [aab] 是不符合要求的组合: 组合内元素的位置随意,即 [ab] 和 [ba] 视为同一种组合:

  • php回溯算法计算组合总和的实例代码

    给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的每个数字在每个组合中只能使用一次. 说明 所有数字(包括目标数)都是正整数. 解集不能包含重复的组合. 实例 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]] 解题思路 直接参考回溯算法团灭排列/

  • 分析Java设计模式之组合模式

    目录 一.概述 二. 模式定义 三. 模式结构 四. 模式实现 五. 模式优缺点 5.1.优点 5.2.缺点 六. 模式适用场景 七. 模式总结 一.概述 我们对于这个图片肯定会非常熟悉,这两幅图片我们都可以看做是一个文件结构,对于这样的结构我们称之为树形结构.在数据结构中我们了解到可以通过调用某个方法来遍历整个树,当我们找到某个叶子节点后,就可以对叶子节点进行相关的操作.我们可以将这颗树理解成一个大的容器,容器里面包含很多的成员对象,这些成员对象即可是容器对象也可以是叶子对象.但是由于容器对象

  • Java设计模式之组合模式的示例详解

    目录 定义 原理类图 案例 需求 方案 分析 总结 定义 组合模式,又叫部分整体模式,它创建了对象组的数据结构(将对象组合成树状结构,用来表示部分整体的层级关系)组合模式使得用户对单个对象和组合对象的访问具有一致性 原理类图 Component :这是组合模式中的抽象构件,他里面定义了所有类共有的默认行为,用来访问和管理Component的子部件,Component可以是抽象类,也可以是接口 leaf :在组合模式中表示叶子节点,叶子节点没有子节点了,他是最末端存放数据的结构 Composite

随机推荐