阵列的组合总和 - 动态规划 - 修复需要 [英] combination sum of array - dynamic programming - fix needed
问题描述
我已经实现c从输入数组中的元素得到一个目标总和输出所有不同的独特的可能性的$ C $。例如，给定改编 - ＆GT; [1，2，3，5，6，7，10] 和8，输出应该是 [1，2，5]，[1,7目标总和]，[2,6]，[3,5] 。在我下面的code，我得到一个额外的 [2，3] 输出。同时对33的目标，以相同的输入列表，上面我得到奇怪的结果，我在这里需要解决这个code一些帮助。
公共类CombinationSum {
公共静态无效的主要（字串[] args）{
名单＆LT;整数GT;临时=新的ArrayList＆LT;整数GT;（）;
名单＆LT;设置＆LT;整数GT;＆GT; resultList =新的ArrayList＆LT;设置＆LT;整数GT;＆GT;（）;
INT [] ARR = {10,1,2,7,6,3,5};
Arrays.sort（ARR）;
的System.out.println（Arrays.toString（ARR））;
INT目标= 8;
sumCombinations（resultList，温度，目标，编曲，0）;
System.out.printf（目标是：％s; resultList为％s％N，目标resultList）;
INT TARGET2 = 33;
名单＆LT;整数GT; TEMP2 =新的ArrayList＆LT;整数GT;（）;
名单＆LT;设置＆LT;整数GT;＆GT; resultList2 =新的ArrayList＆LT;设置＆LT;整数GT;＆GT;（）;
sumCombinations（resultList2，TEMP2，TARGET2，编曲，0）;
System.out.printf（目标是：％s; resultList为％s％N，TARGET2，resultList2）;
}
公共静态无效sumCombinations（名单＆LT;设置＆LT;整数GT;＆GT; resultList，名单，其中，整数GT;温度，INT目标，INT [] ARR，
INT启动）{
对于（INT I =启动; I＆LT; arr.length;我++）{
如果（ARR [我] ==目标）{
temp.add（ARR [I]）;
设置＆LT;整数GT;从无到有=新的HashSet＆LT;整数GT;（临时）;
如果（！resultList.contains（从零开始））
resultList.add（刮）;
}
否则，如果（目标＆GT;常用3 [I]）{
temp.add（ARR [I]）;
sumCombinations（resultList，温度，目标ARR [我]，编曲，开始+ 1）;
}
否则返回;
如果（temp.size（）大于0）
temp.remove（temp.size（） - 1）;
}
}
}
输出：
目标为8; resultList是[[1，2，5]，[1，7]，[2，3]，[2,6]，[3,5]]`
目标是33; resultList是[[1，2，3，7，10]，[1，2，5，10]，[1，2，6，7，10]，
并[1,2，10]，[1，3，6，10]，[1，3，5，7，10]，[1，3，6，7，10]，[1，5，7，10 ]
[1，5，6，10]，[1，5，6，7]，[1，6,7]，[1,6，10]，[2，3，6，10]，[2,5 7，10]，
[2，6，7，10]，[2，3，5，10]，[2，3，5，6，7，10]，[2，3，7]，[2，5，6，10 ]
[2，5,7]，[2，5，6，7]，[2，6,7]，[2,7，10]，[3,7，10]，[3，5，7，10 ]
[3，5，6，10]，[3，6，7]，[3，5，6，7]，[3,5，10]，[3，6，7，10]，[3，10 ]
[5，6，7]，[5，6，7，10]，[5,6，10]，[5,7]，[6,7]，[6,7，10]]
您递归调用
sumCombinations（resultList，温度，目标 - 常用3 [I]，编曲，开始+ 1）;
应该是这样的：
sumCombinations（resultList，温度，目标 - 常用3 [I]，编曲，I + 1）;
由于路上这个递归做，一旦你添加的数量采摘previous 0的我为号就已经被认为是，你只需要调用温度所有组合。 .I-1 sumCombinations 最后一次加入后的测试组合。
这造成一些数字必须重新考虑并多次添加，例如错误的溶液[2，3]为8竟是[2，3,3]，当转换为集中删除重复3。
I have implemented the code to output all the different unique possibilities of getting a target sum from the elements of input array. for example given the arr -> [1, 2, 3, 5, 6, 7, 10] and target sum of 8, the output should be [1, 2, 5], [1, 7], [2, 6], [3, 5]. In my code below, I get an extra [2, 3] in the output. Also for the target of 33, with the same input list as above I get strange results I need some assistance here in fixing this code.
public class CombinationSum {
public static void main(String[] args){
List<Integer> temp = new ArrayList<Integer>();
List<Set<Integer>> resultList = new ArrayList<Set<Integer>>();
int[] arr={10,1,2,7,6,3,5};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
int target=8;
sumCombinations(resultList, temp, target, arr, 0);
System.out.printf("target is %s; resultList is %s%n",target,resultList);
int target2=33;
List<Integer> temp2 = new ArrayList<Integer>();
List<Set<Integer>> resultList2 = new ArrayList<Set<Integer>>();
sumCombinations(resultList2, temp2, target2, arr, 0);
System.out.printf("target is %s; resultList is %s%n",target2,resultList2);
}
public static void sumCombinations(List<Set<Integer>> resultList, List<Integer> temp, int target, int[] arr,
int start){
for (int i=start;i<arr.length;i++){
if (arr[i]==target){
temp.add(arr[i]);
Set<Integer> scratch = new HashSet<Integer>(temp);
if (!resultList.contains(scratch))
resultList.add(scratch);
}
else if (target>arr[i]){
temp.add(arr[i]);
sumCombinations(resultList, temp, target-arr[i], arr, start+1);
}
else return;
if (temp.size()>0)
temp.remove(temp.size()-1);
}
}
}
Output:
target is 8; resultList is [[1, 2, 5], [1, 7], [2, 3], [2, 6], [3, 5]]`
target is 33; resultList is [[1, 2, 3, 7, 10], [1, 2, 5, 10], [1, 2, 6, 7, 10],
[1, 2, 10], [1, 3, 6, 10], [1, 3, 5, 7, 10], [1, 3, 6, 7, 10], [1, 5, 7, 10],
[1, 5, 6, 10], [1, 5, 6, 7], [1, 6, 7], [1, 6, 10], [2, 3, 6, 10], [2, 5, 7, 10],
[2, 6, 7, 10], [2, 3, 5, 10], [2, 3, 5, 6, 7, 10], [2, 3, 7], [2, 5, 6, 10],
[2, 5, 7], [2, 5, 6, 7], [2, 6, 7], [2, 7, 10], [3, 7, 10], [3, 5, 7, 10],
[3, 5, 6, 10], [3, 6, 7], [3, 5, 6, 7], [3, 5, 10], [3, 6, 7, 10], [3, 10],
[5, 6, 7], [5, 6, 7, 10], [5, 6, 10], [5, 7], [6, 7], [6, 7, 10]]
Your recursive call
sumCombinations(resultList, temp, target - arr[i], arr, start + 1);
should be like this:
sumCombinations(resultList, temp, target - arr[i], arr, i + 1);
Because the way this recursion is done once you are adding the number i to temp all the combinations of picking the previous 0..i-1 numbers will already be considered, you only have to call sumCombinations to test combinations after the last addition.
This caused some numbers to be reconsidered and added multiple times, for example the wrong solution [2, 3] for 8 was actually [2, 3 ,3] that when converted to a Set deleted the repeated 3.
这篇关于阵列的组合总和 - 动态规划 - 修复需要的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
