阵列的组合总和 - 动态规划 - 修复需要组合、阵列、总和、动态

由网友(承諾丶洳風般過往雲煙)分享简介：我已经实现c从输入数组中的元素得到一个目标总和输出所有不同的独特的可能性的$ C $。例如，给定改编 - ＆GT; [1，2，3，5，6，7，10] 和8，输出应该是 [1，2，5]，[1,7目标总和]，[2,6]，[3,5] 。在我下面的code，我得到一个额外的 [2，3] 输出。同时对33的目标，以相同的输入列表...

我已经实现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]]

解决方案 C编程最大子数组的和的动态规划的解法

您递归调用

  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.

阅读全文

相关专题：组合；阵列；总和；动态；发布时间：2023-09-11 06:32:01