深搜之搜索树

深碍√TFBOYSˉ_ 2022-08-25 08:27 174阅读 0赞

给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。

输入：

n=4

a=\{1,2,4,7\}

k=13

输出：

Yes（13=2+4+7）

经典深搜问题：递归代码：

#include <cstdio>
    int a[30];int n,k;
    bool dfs(int i,int sum)  //前i项之和sum
    {
        if(i==n)
            return sum==k;
        if(dfs(i+1,sum))  //放入第i个
            return true;
        if(dfs(i+1,sum+a[i]))  //不放入第i个
            return true;
    }
    int main()
    {
        while(~scanf("%d%d",&n,&k))
        {
            for(int i=0;i<n;i++)
                scanf("%d",&a[i]);
            if(dfs(0,0))
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }

如果要求保存相加的每一个数，可以这样实现：

#include <iostream>
    #include <vector>
    using namespace std;
    int a[4]={1,2,4,7},k;
    vector<int> ans;
    void dfs(int i,int sum)
    {
    	if(i==4){
    		if(sum==k)
    	   	{
       			for(int i=0;i!=ans.size();i++)cout<<ans[i]<<" ";
    			cout<<endl;
    			return ;
       		}
       		else 
    		 return ;
    	}
    	dfs(i+1,sum);
    	ans.push_back(a[i]);
    	dfs(i+1,sum+a[i]);
    	ans.pop_back();
    	return ;
    }
    int main()
    {
    	 k=7;
    	 dfs(0,0);
    }

发表评论取消回复

表情：

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

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

相关阅读

相关广搜与深搜

一、深搜属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次；

绝地灬酷狼/ 2024年01月08日 13:19/ 0 赞/ 55 阅读

相关 leetcode 子集深搜

一(每一个数选或不选 > 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 > 说明：解集不能包含重复的子集。 > 示例: > 输入:

Dear 丶/ 2023年08月17日 15:43/ 0 赞/ 101 阅读

相关素数环（深搜）

描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的

亦凉/ 2022年09月28日 13:01/ 0 赞/ 155 阅读

相关深搜之搜索树

给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。输入： n=4 a=\{1,2,4,7\} k=13 输出： Yes（13

深碍√TFBOYSˉ_/ 2022年08月25日 08:27/ 0 赞/ 175 阅读

相关经典搜索（深搜+剪枝+Java细节注意）

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

你的名字/ 2022年08月20日 13:24/ 0 赞/ 135 阅读

相关数据结构之图【深搜，广搜】

package com.zhiru; import java.util.Queue; import java.util.LinkedList;

心已赠人/ 2022年08月11日 15:29/ 0 赞/ 181 阅读

相关深搜和广搜（初学者）

搜索入门最近对搜索有了一点浅显的了解，想跟大家分享分享。说起来我也是初学者，恰巧有些自己的理解，想起来自己开始学习搜索的情况，真是一把鼻子一把

淩亂°似流年/ 2022年06月08日 09:08/ 0 赞/ 296 阅读

相关 Rescue-HDU-深搜

Rescue Problem Description Angel was caught by the MOLIGPY! He was put in pri

╰半橙微兮°/ 2022年06月05日 06:26/ 0 赞/ 210 阅读

相关数据结构之图论之深搜广搜

一、问题引入有一天，小哈一个人去玩迷宫。但是方向感不好的小哈很快就迷路了。小哼得知后便去解救无助的小哈。此时的小哼已经弄清楚了迷宫的地图，现在小哼要以最快的速度去解救小

ゞ浴缸里的玫瑰/ 2022年05月12日 09:04/ 0 赞/ 237 阅读

相关【深搜】单词方阵

声明 -------------------- 我的码风可能有点和别人不太一样（其实就是有点奇怪），大家重在意会即可。 [原题传送门][Link 1] 前言

叁歲伎倆/ 2021年12月24日 08:31/ 0 赞/ 260 阅读