`

深度优先遍历------部分和问题

    博客分类:
  • java
 
阅读更多
代码如下:


package com.chapterOne.exercise;

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

/**
 * Created by yangjianzhou on 2014/8/15 19:56.
 * TODO : 给定a1,a2,a3,......an,判断是够可以从中选取若干个数,使它们的和恰好为k
 */
public class PartSum {

    private static int n = 9;
    private static int target = 23;
    private static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    private static List<String> result = new ArrayList<String>();

    public static void main(String[] args) {
            System.out.println(dfs(0,0));
            for(String str : result){
                System.out.print(str + "---");
            }
    }

    private static boolean dfs(int i, int sum) {
        if (i == n) {
            return sum == target;
        }
        if (dfs(i + 1, sum)) {
            return true;
        }

        if (dfs(i + 1, sum + arr[i])) {
            result.add(String.valueOf(arr[i]));
            return true;
        }
        return false;
    }
}



运行结果如下:


true
9---8---6---
分享到:
评论

相关推荐

    无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf

    无向图建立、深度优先遍历和广度优先遍历实现算法 本文将详细介绍无向图的建立、深度优先遍历和广度优先遍历的实现算法。这些算法是数据结构中非常重要的内容,掌握它们对后续学习和应用非常重要。 一、无向图的...

    图的深度优先遍历算法源码

    本文将详细解析一个C语言实现的深度优先遍历算法源码,旨在帮助读者深入理解DFS的原理和具体实现。 #### 算法核心概念 在进行深度优先遍历前,我们需要理解几个关键概念: 1. **邻接表**:用于存储图的数据结构,每...

    MATLAB实现迷宫的递归深度优先遍历算法

    深度优先遍历是一种图遍历策略,特别适合解决寻找路径的问题,如在迷宫中找到从起点到终点的所有可能路径。 首先,我们要理解迷宫可以被抽象为一个二维矩阵,其中0代表可通行的路径,1代表障碍物。DFS算法的基本...

    图的邻接表存储实现及深度优先遍历

    - `DFS_IN(int i)`函数:这是深度优先遍历的核心部分。它首先标记当前节点已访问,然后遍历当前节点的相邻节点,对未访问的节点递归调用`DFS_IN()`。 5. **深度优先遍历(DFS)**:DFS是一种遍历图的方法,从起点...

    数据结构-c语言-带main函数-图7.3-图的遍历-深度优先搜索-递归方法-邻接矩阵-有向图。

    在CFree软件环境下运行这段代码,用户可以交互式地输入有向图的顶点和边,然后观察深度优先搜索的遍历结果,这对于理解图的遍历算法及其在C语言中的实现非常有帮助。这个程序也可以扩展应用于解决其他与图相关的算法...

    C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列。

    它接受一个无向图`G`和一个顶点索引`k`作为参数,从顶点`k`开始进行深度优先遍历。 4. **完整遍历**:由于一个图可能包含多个不连通的子图,因此还需要一个辅助函数`DFStravers()`来确保遍历整个图。该函数首先标记...

    图的深度优先遍历

    常见的图遍历方法有两种:深度优先遍历(Depth-First Search, DFS)和广度优先遍历(Breadth-First Search, BFS)。本篇文章将重点介绍深度优先遍历,并通过一个具体的例子来展示如何实现该算法。 #### 二、深度...

    基于深度优先遍历的迷宫生成程序

    深度优先遍历(Depth-First Search,简称DFS)是一种用于遍历或搜索树或图的算法,它在解决迷宫生成问题中起到了关键作用。在本文中,我们将深入探讨基于C#实现的DFS迷宫生成程序,以及如何利用VS2008进行项目构建和...

    图的深度、广度优先遍历(c语言).rar

    在这个压缩包中,包含了一个用C语言实现的程序,用于执行图的深度优先遍历(DFS, Depth-First Search)和广度优先遍历(BFS, Breadth-First Search)。以下是这两个遍历方法的详细解释: 1. **深度优先遍历(DFS)*...

    图的深度优先遍历 数据结构

    根据给定的文件标题“图的深度优先遍历 数据结构”、描述以及部分代码内容,我们可以提炼出关于图数据结构中的深度优先遍历(Depth-First Search, DFS)与广度优先遍历(Breadth-First Search, BFS)的相关知识点。...

    数据结构实验3.4:以邻接表为存储结构的图的深度、宽度优先遍历.doc

    数据结构实验报告主要探讨了如何使用邻接表作为存储结构来实现图的深度优先遍历(DFS)和广度优先遍历(BFS)。在计算机科学中,图是一种表示对象间关系的数据结构,邻接表是高效存储无向图或有向图的一种方式,它...

    图的存储与深度广度遍历输出

    本文主要介绍邻接表的存储方式以及基于此的深度优先遍历和广度优先遍历算法。 #### 二、邻接表的基本概念 邻接表是一种链式存储结构,它为图中的每个顶点建立一个单链表,链表中的每个结点称为表结点或边结点,用来...

    基于C++进行图的深度优先遍历(高级语言程序设计实验)

    深度优先遍历(Depth-First Search, DFS)是图遍历的一种算法,尤其适用于寻找图中的路径或者判断图是否连通。本实验是基于C++语言进行图的深度优先遍历实践,旨在加深对高级语言程序设计的理解。 首先,我们要理解...

    图的深度优先和广度优先遍历源码

    本资料包含的是Java实现的图的深度优先遍历(DFS, Depth First Search)和广度优先遍历(BFS, Breadth First Search)的源码,方便开发者直接运行和学习。 深度优先遍历是从一个顶点出发,尽可能深地搜索图的分支。...

    邻接表存储的图的DFS,BFS遍历

    本文将深入探讨使用邻接表存储的图进行深度优先遍历(DFS)和广度优先遍历(BFS)的方法。 **邻接表** 是一种高效的空间优化存储方式,尤其适用于稀疏图(边的数量远小于节点数量的平方)。在邻接表中,每个节点有...

    图和图的遍历实验操作

    实验中给出了一个具体示例,展示了如何建立一个包含5个顶点和7条边的有向图,并进行深度优先遍历。 在实际编程中,为了确保程序的健壮性,还需要考虑错误处理,例如输入验证、内存分配失败等情况。此外,对于大型图...

    数据结构学习。C语言实现算法:图的深度优先遍历与广度优先遍历、 二叉查找树、 二叉树 、堆排序算法、 KMP算法、 链表.zip

    本压缩包提供了一份针对新手学习C语言实现数据结构和算法的资源,特别关注了图的深度优先遍历与广度优先遍历、二叉查找树、二叉树、堆排序算法以及KMP算法。以下是这些知识点的详细说明: 1. **图的深度优先遍历...

    深度优先遍历复原二阶魔方python代码+详细注释+实验报告详细步骤

    在本文中,我们将深入探讨如何使用Python编程语言和深度优先遍历算法来解决二阶魔方的复原问题。二阶魔方,也被称为迷你魔方,是比标准三阶魔方更小、更简单的版本,但其复原原理基本相同。深度优先遍历是一种在图或...

    图的遍历,深度优先搜索,广度优先搜索,生成最小生成树

    总之,图的遍历、深度优先搜索、广度优先搜索和生成最小生成树是图论和算法基础的重要组成部分,它们在许多计算问题中都有应用,如网络路由、社交网络分析、软件工程等。理解和掌握这些概念有助于提升编程能力,解决...

Global site tag (gtag.js) - Google Analytics