Я наконец-то нашел лучший способ решить эту проблему.И я хотел бы поделиться с людьми, которые заинтересованы в этом вопросе.Код также может работать с дублирующимися элементами во входном массиве.
Я изменил логику этой проблемы.Дерево рекурсии для этого кода показано следующим образом.По сути, это двоичное дерево, и каждая ветвь обозначает, добавлять ли элемент в массив или нет.Индекс массива - это глубина этого дерева.
/ \
arr[0] = 3 3(add 3) 0(don't add 3) depth(index of the arr) == 0
/ \ / \
arr[1] = 1 1+3 0+3 1+0 0+0 depth == 1
/ \ / \ / \ / \
arr[2] = 2 2+4 0+4 2+3 0+3 2+1 0+1 2+0 0+0 depth == 2
/\ /\ /\ /\ /\ /\ /\ /\
......
Дерево, представленное выше, является полным решением для сумм всех подмножеств массива.И, конечно же, мы можем остановить любую ветвь, указав критерий остановки для этой конкретной проблемы:
// base case 1: found the answer
if(curSum == target){
ret.add(new ArrayList<>(part));
return;
}
Действительный код моей проблемы показан следующим образом:
public static List<List<Integer>> twoPartSum2(int[] arr){
// corner case
List<List<Integer>> ret = new ArrayList<>();
List<Integer> part = new ArrayList<>();
if(arr == null || arr.length <= 1){
ret.add(part);
return ret;
}
// usual case
Arrays.sort(arr); // make sure the same numbers will be lined together
int sum = 0;
for(int i : arr){
sum += i;
}
helper2(arr, 0, sum/2, 0, ret, part);
return ret;
}
private static void helper2(int[] arr, int curSum ,int target, int index, List<List<Integer>> ret, List<Integer> part){
// base case 1: found the answer
if(curSum == target){
ret.add(new ArrayList<>(part));
return;
}
// base case 2: solution not found
if(index == arr.length || curSum > target){
return;
}
// recursion case 1: adding current element in the candidate list ("part")
part.add(arr[index]);
helper2(arr, curSum + arr[index], target,index + 1,ret, part);
part.remove(part.size()-1);
// deduplicate the same elements
while(index + 1 < arr.length && arr[index] == arr[index+1]){
index++;
}
// recursion case 2: not adding current element in the candidate list ("part")
helper2(arr, curSum, target, index + 1,ret,part);
}
Обратите внимание, что для дедупликации нашего решения мы должны пропустить одни и те же элементы в нашем массиве, именно поэтому массив сортируется в самом начале Arrays.sort(arr); А затем у нас есть ниже, чтобы пропустить одинаковые элементы в каждомlayer.
// deduplicate the same elements
while(index + 1 < arr.length && arr[index] == arr[index+1]){
index++;
}
Например, если наш массив [1,1,1,3].Тогда у нас будет дерево рекурсии, показанное следующим образом:
/ \
arr[0] = 1 1 0
/ \ | (the other two '1's are skipped)
arr[1] = 1 1+1 0+1 |
/ \ | | (the other one '1' is skipped)
arr[2] = 1 1+2 0+2 | |
/ \ / \ / \ / \
arr[3] = 3 3+3 0+3 3+2 0+2 3+1 0+1 3+0 0+0
Ответ: 6, 3 , 5, 2, 4, 1, 3 , 0
Некоторые из вас могут спросить, почему у нас два 3?Ну, на самом деле, они отличаются 3 в этой задаче, так как первый 3 получается 1 + 1 + 1, а второй из 3, последний элемент в массиве [1,1,1,3].В результате они по-прежнему являются различными решениями этой проблемы.
Логика, которую я использовал ранее в этом вопросе, все еще может работать, но я предпочитаю не публиковать ее в данный момент, поскольку она более запутанная.Однако, если кто-то все еще интересуется этой проблемой, пожалуйста, оставьте комментарий, и я обновлю его, когда я буду свободен.Спасибо!