欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2023-12-22 19:38:58
...
代码如下:


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---

上一篇:

下一篇: