java - 从二维数组中查找唯一的总和，其中每个数组贡献一个值，该值的总和必须是唯一的

Question

目标是找到所有唯一的和，这些和可以通过添加每个数组的一个 int 来创建，但限制是每个整数值在每个最终和中只能使用一次。例如:

int[][] data = { [ 1, 2, 3], [ 1, 2, 3, 4], [ 4, 5, 6] }

变成 //int[] 路径 = [ int in data[0] , int in data[1] , int in data[2] ]

int[][] paths {
[ 1, 2, 4 ] , [ 1, 2, 5 ] , [ 1, 2, 6 ] , 
[ 1, 3, 4 ] , [ 1, 3, 5 ] , [ 1, 3, 6 ] , 
[ 1, 4, 5 ] , [ 1, 4, 6 ] ,
[ 2, 1, 4 ] , [ 2, 1, 5 ] , [ 2, 1, 6 ] ,
[ 2, 3, 4 ] , [ 2, 3, 5 ] , [ 2, 3, 6 ] ,
...
[ 3, 4, 5 ] , [ 3, 4, 6 ]
}

我已经直观地对这些进行了排序，以使过程更加清晰，希望有所帮助。 路径根本不是必需的，但我在解决这个问题的两次尝试中都使用了这种方法，它说明了我如何看待这个问题。

最后的结果应该是这样的:

int[] sums = [ 7, 8, 9, 10, 11 .... , 13 ]

哪里 7 = 1 + 2 + 4(和重复项)、8 = 1 + 2 + 5、9 = 1 + 2 + 6、...、13 = 3 + 4 + 6

我希望我对问题的解释对您来说是清楚的，并且这对您来说也是一个新问题。

我尝试了一种使用 TreeNodes 的方法，效果很好，但我认为我应该能够提高速度复杂性，因为例如我得到分支:1-2-4 和 2-1-4，如上所述。最终对于解决方案来说，第二个分支根本没有必要。基本上它只是一棵树，不允许 child 和 parent 有相同的值(value)。

我暂时保留我的代码，因为我觉得它不一定有帮助，如果我错了，请告诉我。

如果您抽出时间思考一下问题并以任何方式向我提供反馈，我将不胜感激。

我觉得在放置数字之前迭代所有可能的分支来检查它是否包含相同的数字是一个巨大的时间消耗。所以我摆弄了类似的东西，这至少稍微提高了空间复杂性。不幸的是，删除重复元素仍然非常耗时，并且在数组中具有相似元素时提高速度的同时，当这些元素不同时，这是一个巨大的瓶颈。

public static ArrayList<Integer[]> createMultiples(int[][] input) {
            if (input.length == 0) return null;
            int count = 0;
            ArrayList<Integer[]> multiples = new ArrayList<Integer[]>();
            for (int val : input[count]) {
                Integer[] thisvals = new Integer[input.length];
                thisvals[count] = Integer.valueOf(val);
                multiples.add(thisvals);
            }
            if (count + 1 == input.length) return multiples;
            return createMultiples(multiples ,input, ++count);
        }

        public static ArrayList<Integer[]> createMultiples(
ArrayList<Integer[]> multiples, int[][] input, int count) {
            ArrayList<Integer[]> newBranches = new ArrayList<Integer[]>();
            for (int val : input[count]) {
                for (int i = 0; i < multiples.size(); i++) {
                    Integer[] trunk = multiples.get(i);
                    if (!arrContains(trunk, Integer.valueOf(val))) {
                        if (trunk[count] == null) trunk[count] = Integer.valueOf(val);
                        else {
                            Integer[] newBranch = trunk.clone();
                            newBranch[count] = Integer.valueOf(val);
                            newBranches.add(newBranch);
                        }
                    }
                }
            }
            for (Integer[] branch : newBranches) multiples.add(branch);
            multiples = removeDuplicatePaths(multiples);
            if (count + 1 == input.length) return multiples;
            return createMultiples(multiples, input, ++count);
        }

public static ArrayList<Integer[]> removeDuplicatePaths(ArrayList<Integer[]> arrList) {
    ArrayList<Integer[]> retList = new ArrayList<Integer[]>();
    loop: for ( int i = 0; i < arrList.size(); i++ ) {
        //get element
        Integer[] toEval = arrList.get(i);
        //sort element
        Arrays.sort(toEval, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 == null && o2 == null) {
                    return 0;
                }
                if (o1 == null) {
                    return 1;
                }
                if (o2 == null) {
                    return -1;
                }
                return o1.compareTo(o2);
            }});
        //check if element is in new list
        for ( int j = 0; j < retList.size(); j++ ) {
            if (Arrays.equals(retList.get(j), toEval)) continue loop;
        }
        retList.add(toEval);
    }
    return retList;
}

Answer 1

你是对的，保存所有分支会占用大量空间并且很复杂。你实际上只需要最后的总和。除了所有分支之外，你还能保存一些东西吗？