如何构建复杂度为 O(n) space 的树？

Question

问题

给定一组整数，找出总和为 100,000,000 的这些整数的子集。

解决方案

我正在尝试构建一棵树，其中包含给定集合的所有组合以及总和。例如，如果给定的集合看起来像 0,1,2，我将构建以下树，检查每个节点的总和：

                    {}
        {}                      {0}
  {}         {1}         {0}          {0,1}
{}  {2}  {1}   {1,2}  {0}   {2}   {0,1}   {0,1,2}

因为我保留了每个节点的整数数组和总和，我应该只需要内存中树的底部（当前）级别。

问题

我当前的实现将在内存中维护整个树，因此使用了太多的堆 space。

如何更改我当前的实现，以便 GC 处理我的上层树级别？

（目前我只是在找到目标总和时抛出 RuntimeException，但这显然只是为了玩）

public class RecursiveSolver {
    static final int target = 100000000;
    static final int[] set = new int[]{98374328, 234234123, 2341234, 123412344, etc...};

    Tree initTree() {
        return nextLevel(new Tree(null), 0);
    }

    Tree nextLevel(Tree currentLocation, int current) {
        if (current == set.length) { return null; }
        else if (currentLocation.sum == target) throw new RuntimeException(currentLocation.getText());
        else {
            currentLocation.left = nextLevel(currentLocation.copy(), current + 1);
            Tree right = currentLocation.copy();
            right.value = add(currentLocation.value, set[current]);
            right.sum = currentLocation.sum + set[current];
            currentLocation.right = nextLevel(right, current + 1);
            return currentLocation;
        }
    }

    int[] add(int[] array, int digit) {
        if (array == null) {
            return new int[]{digit};
        }
        int[] newValue = new int[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            newValue[i] = array[i];
        }
        newValue[array.length] = digit;
        return newValue;
    }

    public static void main(String[] args) {
        RecursiveSolver rs = new RecursiveSolver();
        Tree subsetTree = rs.initTree();
    }
}

class Tree {
    Tree left;
    Tree right;
    int[] value;
    int sum;

    Tree(int[] value) {
        left = null;
        right = null;
        sum = 0;
        this.value = value;
        if (value != null) {
            for (int i = 0; i < value.length; i++) sum += value[i];
        }
    }

    Tree copy() {
        return new Tree(this.value);
    }
}

Answer 1

在仔细考虑了 erip 的评论之后，我意识到他是对的 - 我不应该使用树来实现这个算法。

蛮力通常是 O(n*2^n)，因为 2^n 个子集有 n 个附加项。 ~~因为我只对每个节点做一次加法，所以我想出的解决方案是O(2^n)，其中n是给定集合的大小。~~另外，这个算法只是O(n) space 复杂度。由于我的特定问题中原始集合中的元素数量很少（大约 25 个）O(2^n) 复杂性不是太大的问题。

这个问题的动态解是O(t*n)，其中t是目标和，n是元素的数量。因为 t 在我的问题中非常大，所以动态解决方案以非常长的运行时间和高内存使用率结束。

这在我的机器上用了大约 311 毫秒完成了我的特定解决方案，这比我看到的针对这个特定 class 问题的动态编程解决方案有了巨大的改进。

public class TailRecursiveSolver {
    public static void main(String[] args) {
        final long starttime = System.currentTimeMillis();
        try {
            step(new Subset(null, 0), 0);
        }
        catch (RuntimeException ex) {
            System.out.println(ex.getMessage());
            final long endtime = System.currentTimeMillis();
            System.out.println(endtime - starttime);
        }
    }

    static final int target = 100000000;
    static final int[] set = new int[]{ . . . };

    static void step(Subset current, int counter) {
        if (current.sum == target) throw new RuntimeException(current.getText());
        else if (counter == set.length) {}
        else {
            step(new Subset(add(current.subset, set[counter]), current.sum + set[counter]), counter + 1);
            step(current, counter + 1);
        }
    }

    static int[] add(int[] array, int digit) {
        if (array == null) {
            return new int[]{digit};
        }
        int[] newValue = new int[array.length + 1];
        for (int i = 0; i < array.length; i++) {
            newValue[i] = array[i];
        }
        newValue[array.length] = digit;
        return newValue;
    }
}

class Subset {
    int[] subset;
    int sum;

    Subset(int[] subset, int sum) {
        this.subset = subset;
        this.sum = sum;
    }

    public String getText() {
        String ret = "";
        for (int i = 0; i < (subset == null ? 0 : subset.length); i++) {
            ret += " + " + subset[i];
        }
        if (ret.startsWith(" ")) {
            ret = ret.substring(3);
            ret = ret + " = " + sum;
        } else ret = "null";
        return ret;
    }
}

编辑-

上面的代码在 O(n*2^n) 时间内仍然是运行s - 因为 add 方法在 O(n) 时间内运行s。以下代码将运行真正 O(2^n) 时间，并且性能更高，在我的机器上大约 20 毫秒完成。

由于将当前子集存储为 long.

中的位，因此仅限于少于 64 个元素的集合

public class SubsetSumSolver {
    static boolean found = false;
    static final int target = 100000000;
    static final int[] set = new int[]{ . . . };

    public static void main(String[] args) {
        step(0,0,0);
    }

    static void step(long subset, int sum, int counter) {
        if (sum == target) {
            found = true;
            System.out.println(getText(subset, sum));
        }
        else if (!found && counter != set.length) {
            step(subset + (1 << counter), sum + set[counter], counter + 1);
            step(subset, sum, counter + 1);
        }
    }

    static String getText(long subset, int sum) {
        String ret = "";
        for (int i = 0; i < 64; i++) if((1 & (subset >> i)) == 1) ret += " + " + set[i];
        if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + sum;
        else ret = "null";
        return ret;
    }
}

编辑 2 -

这是另一个使用中间相遇攻击的版本，为了将复杂性从 O(2^n) 降低到 O(2^(n/2))。

如果你想将它用于包含 32 到 64 个元素的集合，你应该将表示阶梯函数中当前子集的 int 更改为 long，尽管性能显然会大大提高随着集合大小的增加而减少。如果你想将它用于具有奇数个元素的集合，你应该在集合中添加一个 0 使其成为偶数。

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

public class SubsetSumMiddleAttack {
    static final int target = 100000000;
    static final int[] set = new int[]{ ... };

    static List<Subset> evens = new ArrayList<>();
    static List<Subset> odds = new ArrayList<>();

    static int[][] split(int[] superSet) {
        int[][] ret = new int[2][superSet.length / 2]; 

        for (int i = 0; i < superSet.length; i++) ret[i % 2][i / 2] = superSet[i];

        return ret;
    }

    static void step(int[] superSet, List<Subset> accumulator, int subset, int sum, int counter) {
        accumulator.add(new Subset(subset, sum));
        if (counter != superSet.length) {
            step(superSet, accumulator, subset + (1 << counter), sum + superSet[counter], counter + 1);
            step(superSet, accumulator, subset, sum, counter + 1);
        }
    }

    static void printSubset(Subset e, Subset o) {
        String ret = "";
        for (int i = 0; i < 32; i++) {
            if (i % 2 == 0) {
                if ((1 & (e.subset >> (i / 2))) == 1) ret += " + " + set[i];
            }
            else {
                if ((1 & (o.subset >> (i / 2))) == 1) ret += " + " + set[i];
            }
        }
        if (ret.startsWith(" ")) ret = ret.substring(3) + " = " + (e.sum + o.sum);
        System.out.println(ret);
    }

    public static void main(String[] args) {
        int[][] superSets = split(set);

        step(superSets[0], evens, 0,0,0);
        step(superSets[1], odds, 0,0,0);

        for (Subset e : evens) {
            for (Subset o : odds) {
                if (e.sum + o.sum == target) printSubset(e, o);
            }
        }
    }
}

class Subset {
    int subset;
    int sum;

    Subset(int subset, int sum) {
        this.subset = subset;
        this.sum = sum;
    }
}

Answer 2

问题是NP-complete。

如果你真的想提高性能，那么你必须忘记你的树实现。您要么只生成所有子集并将它们相加，要么使用动态编程。

选择取决于要求和的元素数量和您想要达到的总和。你知道总和是 100,000,000，暴力指数算法在 O(2^n * n) 时间内运行，所以对于小于 22 的数字是有意义的。

在 python 中，您可以通过简单的方式实现此目的：

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

您可以通过使用中间相遇技术（阅读 wiki article）显着提高这种复杂性（牺牲内存）。这会将它减少到 O(2^(n/2))，这意味着它将比 n <~ 53

的 DP 解决方案表现更好

Answer 3

在这里构建树所需的时间和 space 完全没有。

原因是，如果给你

树的一个节点
节点深度
输入元素的有序数组

您可以使用 O(1) 操作简单地计算它的父节点、左子节点和右子节点。当你遍历树时，你可以访问所有这些东西，所以你不需要任何其他东西。

如何构建复杂度为 O(n) space 的树？

How can I build this tree with O(n) space complexity?

java

algorithm

tree

space-complexity

subset-sum

问题

解决方案

问题