조합 합계 배열 - 동적 프로그래밍 - 수정 필요

입력 배열 요소에서 대상 합계를 가져 오는 모든 다른 고유 한 가능성을 출력하는 코드를 구현했습니다. 예를 들어 arr -> [1, 2, 3, 5, 6, 7, 10] 및 대상 합계가 8 인 경우 출력은 [1, 2, 5], [1, 7], [2, 6], [3, 5]이어야합니다. 아래 코드에서는 [2, 3]을 출력합니다. 또한 33의 목표에 대해 위와 같은 입력 목록을 사용하면이 코드를 수정하는 데 도움이 필요한 이상한 결과가 나타납니다.조합 합계 배열 - 동적 프로그래밍 - 수정 필요

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

출력 :

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]]

출처

2014-02-21 brain storm

귀하의 재귀 호출

sumCombinations(resultList, temp, target - arr[i], arr, start + 1);

은 다음과 같이해야합니다 :

sumCombinations(resultList, temp, target - arr[i], arr, i + 1);

방법이 있기 때문에 재귀는 번호 temp에 숫자를 추가하면 이전 0..i-1 숫자를 선택하는 모든 조합이 이미 고려됩니다. 마지막 추가 후 조합을 테스트하기 위해서는 sumCombinations 만 호출하면됩니다.

이로 인해 몇 가지 숫자가 재검토되고 여러 번 추가되었습니다. 예를 들어 8에 대한 잘못된 해결책 [2, 3]은 실제로 [2, 3, 3]이었고 세트로 변환하면 반복되는 3을 삭제했습니다.

출처

2014-02-21 21:50:41 DSquare

감사합니다, 중요한 관찰입니다. 하나의 일이지만, intial sorting없이이 작업을하기 위해; 'sumCombinations (resultList, temp, target + temp.remove (temp.size() - 1), arr, i + 1)의 재귀 호출에 대해 else return;을 대체해야합니까? –

정확히' 그렇지 않으면'이전에'else if (target> arr [i])'가 정렬되지 않았다면 의미가 없습니다. 따라서 재 작업을 원할 경우 두 부분을 적절하게 변경해야합니다. 그러나 정렬은 괜찮습니다. 알고리즘의 나머지 부분에 비해 매우 빠르며 재귀 분기를 매우 쉽게자를 수 있습니다. – DSquare

조합 합계 배열 - 동적 프로그래밍 - 수정 필요

답변

관련 문제