DFS-部分和

怼烎@ 2023-07-09 08:25 41阅读 0赞

## 题目描述 ##

给定整数序列a1,a2,…,an,判断是否可以从中选出若干数,使它们的和恰好为k.

1≤n≤20
    
    -10^8≤ai≤10^8
    
    -10^8≤k≤10^8

**样例:输入**

n=4
    a={
        1,2,4,7}
    k=13

**输出:**

Yes (13 = 2 + 4 + 7)

## 解法一 ##

import javafx.scene.transform.Scale;
    
    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class dfs_部分和 {
        
        static void dfs(int []a, int k, int cur, ArrayList<Integer> ints){
        
            if (k==0){
        
                System.out.println("YES");
                System.exit(0);
            }
            if (cur==a.length||k<0){
        
                return;
            }
    
            dfs(a,k,cur+1,ints);
            ints.add(a[cur]);
            int index=ints.size()-1;
            dfs(a,k-a[cur],cur+1,ints);
            ints.remove(index);
        }
        public static void main(String[] args) {
        
    
            Scanner sc =new Scanner(System.in);
            int n=sc.nextInt();
            int[] a=new int[n];
            for (int i = 0; i <n ; i++) {
        
                a[i]=sc.nextInt();
            }
            int k=sc.nextInt();
            dfs(a,0,k,new ArrayList<Integer>());
        }
    }

## 最优解法 ##

import javafx.scene.transform.Scale;
    
    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class dfs_部分和 {
        
        static void dfs(int []a, int k, int cur, ArrayList<Integer> ints){
        
            if (k==0){
        
                System.out.println("YES");
                System.exit(0);
            }
            if (cur==a.length||k<0){
        
                return;
            }
    
            dfs(a,k,cur+1,ints);
            ints.add(a[cur]);
            int index=ints.size()-1;
            dfs(a,k-a[cur],cur+1,ints);
            ints.remove(index);
        }
        public static void main(String[] args) {
        
    
            Scanner sc =new Scanner(System.in);
            int n=sc.nextInt();
            int[] a=new int[n];
            for (int i = 0; i <n ; i++) {
        
                a[i]=sc.nextInt();
            }
            int k=sc.nextInt();
            dfs(a,0,k,new ArrayList<Integer>());
        }
    }

转载：https://www.cnblogs.com/xiaoyh/p/10346658.html

发表评论取消回复

表情：

评论列表（有 0 条评论，41人围观）

还没有评论，来说两句吧...

相关阅读

相关 nyoj 1282 部分和问题(入门题)（dfs）

部分和问题(入门题) 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 0 描述给你n个数(a1,a2,a3.......an) ,是否存在某

不念不忘少年蓝@/ 2024年02月17日 20:21/ 0 赞/ 40 阅读

相关 pandas中 df[‘X‘]和df[[‘X‘]]的不同

样例数据 df = pd.DataFrame(\{‘X’: \[1, 2, 7, 5, 10\], ‘Y’: \[4, 3, 8, 2, 9\]\}) ![在这里插入

青旅半醒/ 2023年09月23日 12:57/ 0 赞/ 120 阅读

相关 DFS-部分和

题目描述给定整数序列a1,a2,…,an,判断是否可以从中选出若干数,使它们的和恰好为k. 1≤n≤20 -10^8≤ai≤10^8

怼烎@/ 2023年07月09日 08:25/ 0 赞/ 42 阅读

相关 dfs和bfs

https://www.cnblogs.com/wzl19981116/p/9397203.html 1.dfs(深度优先搜索)是两个搜索中先理解并使用的，其实就是暴力把所

àì夳堔傛蜴生んèń/ 2023年03月06日 08:14/ 0 赞/ 46 阅读

相关 dfs和bfs差别_BFS和DFS之间的区别

![0f76213b219d1be3b9b0f435f8e8bbfd.png][] dfs和bfs差别 Here you will learn about differen

古城微笑少年丶/ 2022年12月07日 13:56/ 0 赞/ 208 阅读

相关多重部分和问题 dfs

Description 有n种不同大小的数字，每种各个。判断是否可以从这些数字之中选出若干使它们的和恰好为K。 Input 首先是一个正整数T(1<=T<=100

系统管理员/ 2022年06月16日 03:21/ 0 赞/ 193 阅读

相关 DFS和BFS

include<iostream> include<queue> using namespace std; define MAX 100 class MGraph {

谁践踏了优雅/ 2022年06月15日 03:20/ 0 赞/ 221 阅读

相关模板--bfs和dfs

\[cpp\] [view plain][] [copy][view plain] [print][view plain][?][view plain]

小灰灰/ 2022年06月11日 04:17/ 0 赞/ 224 阅读

相关 dfs解决部分和问题

问题描述：给出n个数，给出和k，能否选出若干个数，使他们的和为k 代码如下 include<stack> include<vector> inclu

布满荆棘的人生/ 2022年05月11日 11:56/ 0 赞/ 238 阅读

相关 linux du和df

当磁盘大小超过标准时会有报警提示，这时如果掌握df和du命令是非常明智的选择。 df可以查看一级文件夹大小、使用比例、档案系统及其挂入点，但对文件却无能为力。 du可以

向右看齐/ 2021年06月24日 13:58/ 0 赞/ 543 阅读