All geek questions in one place

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

Problem

Given a set of integers, find the subset of those integers that add up to 100,000,000.

Decision

I am trying to build a tree containing all the combinations of this set together with the sum. For example, if this set looked like 0,1,2, I would build the following tree, checking the sum on each node:

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

Since I save both an array of integers in each node and the sum,, I only need the lower (current) level of the tree in memory.

Questions

My current implementation will save the whole tree in memory and therefore uses too much heap.

How can I change the current implementation so that the GC takes care of my top levels of the tree?

( 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);
    }
}
+4
3

, , .

,

  • A node
  • node

, , O(1). , , .

+1

NP-complete.

, . , , .

, . , 100,000,000, bruteforce 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 ). O(2^(n/2)), , , DP n <~ 53

+1

erip, , - .

O(n*2^n), n 2^n. node, , , - O(2^n), n - . , O(n) . ( 25) O(2^n) .

O(t*n), t - , n - . t , .

311 , , .

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

EDIT -

- O(n*2^n) - add O(n). O(2^n) , 20 .

64 - long.

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

If you want to use this for sets between 32 and 64 elements, you must change intwhich represents the current subset in the step function to long, although performance will obviously decrease dramatically as the set size increases. If you want to use this for a set with an odd number elements, you must add 0 to the set to make it even numbered.

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;
    }
}
0
source

Source: https://habr.com/ru/post/1648106/

More articles:


All Articles