如何找到如果数组中的任何值加起来为n [英] How to find if any values in array add up to n

问题描述

予具有随机值的数组，和一个目标值。

I have an array of random values, and a target value.

#!/bin/bash
objective='50'
declare -a values=(1 2 2 6 8 14.5 15 28.7 .. 42)

我需要找到一个方法来提取数组中的价值，加起来就是50个号码的组合

I need to find a way to extract any combination of numbers in the array 'values' that add up to 50

该阵列具有重复的，浮点整数。

The array has duplicates, and floating point integers.

一个解决方案集可能是这样的：

A solution set might look like:

50 = 42 + 8
50 = 42 + 6 + 2

起初，我开始在bash嵌套的循环一些，但我很快意识到，这将成倍的增长与我的数组长度。

Initially I started in bash with some nested for loops, however I'm quickly realizing that this will grow exponentially with my array length.

我花了几个java类的大学，但我还是没有经验的编程。我开始想，这可能需要递归。

I took a couple of java classes in college, but I'm still inexperienced in programming. I'm starting to think this may require recursion.

任何人都可以有更多的编程经验，指明了正确的方向？
除了嵌套的循环，是怎么回事，你能解决这个问题？

Can anyone with more programming experience point me in the right direction?
Besides nested for loops, how else could you approach this problem?

推荐答案

您可以使用递归是的，你可以打破阵列成​​子部分（我用列表） 。

You can use recursion yes, you can break the array into sub-parts (I use List).

1. 从父列表以及零索引列表为空启动
2. 遍历从子表的父I + 1 到底，从而增加从您的工作清单0至i
3. 检查的之（计算）等于你的目标

1. Start from 0th index of the Parent list and a blank list
2. Iterate over to subList your Parent from i+1 to the end and thereby increasing your working list from 0 to i
3. Check for the sum (calculated) equals your objective

code：

static Integer[] array = { 1, 2, 2, 6, 8, 14, 15, 28, 30, 32, 12, 48, 6, 42 };
static int objective = 50;

public static void main(String args[]) {
    add(new ArrayList<Integer>(Arrays.asList(array)),
            new ArrayList<Integer>());
}

public static void add(List<Integer> digits, List<Integer> workingList) {

    for (int i = 0; i < digits.size(); i++) {
        // New sublist to store values from 0 to i
        List<Integer> list = new ArrayList<Integer>(workingList);
        list.add(digits.get(i));

        // Here you call this recursively with your Parent list from i+1
        // index and working list from 0 to i
        add(digits.subList(i + 1, digits.size()), list);
    }

    int sum = 0;
    for (int element : workingList) {
        sum += element;
    }

    if (sum == objective) {
        System.out.println(objective + " = "
                + Arrays.toString(workingList.toArray()));
    }

}

输出：

50 = [1, 2, 2, 15, 30]
50 = [1, 2, 6, 8, 15, 12, 6]
50 = [1, 2, 6, 14, 15, 12]
50 = [1, 2, 14, 15, 12, 6]
50 = [1, 2, 15, 32]
50 = [1, 2, 6, 8, 15, 12, 6]
...

这篇关于如何找到如果数组中的任何值加起来为n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！