[Leetcode 216][Medium]组合总和 III--回溯(组合问题)

news/2024/9/20 1:26:28/ 标签: leetcode, 算法, 职场和发展

目录

一、题目描述

二、整体思路

三、代码


一、题目描述

原题地址

二、整体思路

        对于组合问题,首先要想到回溯法。那么可以根据回溯法模版进行设计。

void backtrace(元素){if(满足题目要求的条件){保存目前路径/状态/结果;return;}for循环,往目前状态相邻的所有可能的状态进行遍历{往下一个状态去的所需要进行的操作;backtrace(下一个状态);//递归调用backtrace;回溯操作,还原成目前状态。}}

        理解回溯法的本质是穷举所有可能的状态,通过递归来使得可以在原状态的基础上进入下一个状态,也就是入栈。那么不停地入栈直到没有可进入的状态时,递归函数进行出栈。

        那么函数出栈时,我们需要把当前状态还原成原状态,因为之前进入的下一个状态随着出栈已经结束了。 

三、代码

        

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> temp=new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {backtrace(1,k,n);return res;}void backtrace(int l,int k,int n){//l表示遍历到的数,n表示距离相差之和还有多远if(temp.size()==k){if(n==0){res.add(new ArrayList<>(temp));//不要直接用temp,因为temp是引用,如果直接用temp回溯时会改变temp,res里面的元素也会改变}return;}for(int i=l;i<=9;i++){//所有可能的状态就是1-9temp.add(i);backtrace(i+1,k,n-i);temp.remove(temp.size()-1);}return;}
}


http://www.ppmy.cn/news/1519765.html

相关文章

简述二叉树先序遍历、中序遍历和后序遍历的思想。

先序遍历&#xff08;根左右&#xff09;(DLR) 若二叉树为空&#xff0c;则退出&#xff0c;否则进行下面操作:访问根结点、先序遍历左子树、先序遍历右子树。 中序遍历&#xff08;左根右&#xff09;(LDR) 若二叉树为空&#xff0c;则退出&#xff0c;否则进行下面操作:中…

SOEX从去中心化的链上社交关系到创收策略

是时候摆脱传统的在线社区&#xff0c;真正进入 Web3 了&#xff0c;利用区块链的力量&#xff0c;并理解社交互动的意义远不止分享内容或复制交易。代币化将赋能参与提升到一个全新的水平&#xff0c;并带来一系列新的机会。 社交网络可以发挥强大的作用&#xff0c;尤其是从…

Pytorch中不同的Norm归一化详细讲解

在做项目或者看论文时&#xff0c;总是能看到Norm这个关键的Layer&#xff0c;但是不同的Norm Layer具有不同的作用&#xff0c;准备好接招了吗&#xff1f;&#xff08;本文结论全部根据pytorch官方文档得出&#xff0c;请放心食用&#xff09; 一. LayerNorm LayerNorm的公…

github源码指引:C++嵌入式WEB服务器

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 相关专题&#xff1a; C嵌入式…

Element组件

文章目录 1 Element介绍2 快速入门3 Element组件3.1 Table表格3.1.1 组件演示3.1.2 组件属性详解 3.2 Pagination分页3.2.1 组件演示3.2.2 组件属性详解3.2.3 组件事件详解 3.3 Dialog对话框3.3.1 组件演示3.3.2 组件属性详解 3.4 Form表单3.4.1 组件演示 1 Element介绍 Eleme…

【代码随想录训练营第42期 Day46打卡 - 回文问题 - LeetCode 647. 回文子串 516.最长回文子序列

目录 一、做题心得 二、题目与题解 题目一&#xff1a;647. 回文子串 题目链接 题解1&#xff1a;动态规划 题解2&#xff1a;中心扩展法 题目二&#xff1a;516.最长回文子序列 题目链接 题解1&#xff1a;反转LCS 题解2&#xff1a;动态规划 三、小结 一、做题心得…

react antd点击table行时加选中背景色

在React中使用Ant Design的Table组件时&#xff0c;可以通过rowSelection属性来实现点击行时加亮背景色的功能。 import React from react; import { Table } from antd;const data [{key: 1,name: John Brown,age: 32,address: New York No. 1 Lake Park,},// ... 更多数据…

Leetcode102二叉树的层序遍历(java实现)

今天分享的题目是lee102题&#xff0c;题目的描述如下&#xff1a; 可能做到这道题的小伙伴写过其他关于二叉树的题目&#xff0c;但是一般是使用递归的方式做一个深度遍历&#xff0c;而层序遍历我们该如何做呢&#xff1f; 解题思路&#xff1a;使用一个队列来记录本层节点&a…

docker——compose容器编排!!!

⼀、Docker-compose 定义 1. docker compose 是 docker 官⽅的开源项⽬&#xff0c;负责实现对docker 容器集群的快速编排(容器&#xff0c;依赖&#xff0c;⽹络&#xff0c;挂载。。) 2. compose 是 docker 公司推出的⼀个⼯具软件&#xff0c;可以管理多个docker 容器组成…

手撕Python之序列类型

1.列表---list 索引的使用 当我们有一个数据的时候&#xff0c;我们怎么将这个数据存储到程序呢&#xff1f; 我们定义一个变量&#xff0c;将数据存储在变量中 那么如果有100个数据呢&#xff1f;要定义100个变量吗&#xff1f; 我们是可以用列表这个东西进行多个数据的存…

92. UE5 GAS RPG 使用C++创建GE实现灼烧的负面效果

在正常游戏里&#xff0c;有些伤害技能会携带一些负面效果&#xff0c;比如火焰伤害的技能会携带燃烧效果&#xff0c;敌人在受到伤害后&#xff0c;会接受一个燃烧的效果&#xff0c;燃烧效果会在敌人身上持续一段时间&#xff0c;并且持续受到火焰灼烧。 我们将在这一篇文章里…

[知识分享]华为铁三角工作法

在通信技术领域&#xff0c;尤其是无线通信和物联网领域&#xff0c;“华为铁三角”是华为公司内部的一种销售、交付和服务一体化的运作模式。这种模式强调的是以客户为中心&#xff0c;通过市场、销售、交付和服务三个关键环节的紧密协作&#xff0c;快速响应客户需求&#xf…

upload-labs通关攻略

Pass-1 这里上传php文件说不允许上传 然后咱们开启抓包将png文件改为php文件 放包回去成功上传 Pass-2 进来查看提示说对mime进行检查 抓包把这里改为image/jpg; 放包回去就上传成功了 Pass-3 这里上传php文件它说不允许上传这些后缀的文件 那咱们就可以改它的后缀名来绕过…

HarmonyOS开发实战( Beta5版)AOT编译使用指南

AOT编译使用指南 AOT(Ahead Of Time)即预先编译&#xff0c;在程序运行前&#xff0c;预先编译成高性能机器码&#xff0c;让程序在首次运行就能通过执行高性能机器码获得性能收益 方舟AOT编译器实现了PGO (Profile-Guided-Optimization&#xff09;编译优化&#xff0c;即通过…

Spring Boot 中 `@Transactional` 注解使用示例

Transactional 注解在 Spring Boot 中用于管理事务。它确保在方法执行过程中&#xff0c;所有数据库操作要么全部成功&#xff0c;要么全部回滚&#xff0c;以维护数据的一致性。下面是一些使用 Transactional 的示例&#xff1a; 1. 在服务层使用 Transactional Service pub…

【React】Redux-toolkit 处理异步操作

安装 npm install reduxjs/toolkit react-redux创建 store src\store\index.js import { configureStore } from reduxjs/toolkit; import homeReducer from ./modules/home;const store configureStore({reducer: {home: homeReducer,}, });export default store;创建 Red…

UE4 BuildCookRun中的Archive的含义

在UE4中&#xff0c;Archive、Cook、Stage、Package、Build的次序是怎么样的&#xff1f; 整体打包过程如下: Build -> Cook-> Stage -> Package -> Archive。其中&#xff0c;Archive 的含义是从Staged目录中拷贝文件到一个额外的目录即Archive目录。被称为“归档…

四十五、【人工智能】【机器学习】- Robust Regression(稳健回归)

系列文章目录 第一章 【机器学习】初识机器学习 第二章 【机器学习】【监督学习】- 逻辑回归算法 (Logistic Regression) 第三章 【机器学习】【监督学习】- 支持向量机 (SVM) 第四章【机器学习】【监督学习】- K-近邻算法 (K-NN) 第五章【机器学习】【监督学习】- 决策树…

【Android】repositories和sourceSets指定了 `libs` 目录的区别

repositories { flatDir { dirs libs } } 这段代码的作用是告诉 Gradle 在指定的目录&#xff08;这里是 libs 目录&#xff09;中查找 JAR 文件或 AAR 文件。flatDir 是一种简单的文件目录结构&#xff0c;它不会解析子目录&#xff0c;只会查找指定目录中的文件。 reposito…

Arduino 串口打印小知识点

String str[]{"abc","defg","hijk","lm","n"}; int num; void setup() {Serial.begin(115200);numsizeof(str) /sizeof(str[2]);Serial.print("该数组 str[]的长度&#xff1a;");Serial.print(num); }void loop(…