LeetCode - 조합 합계 II

문제 설명

후보 번호(candidates)와 대상 번호(target)의 모음이 주어지면 후보 번호의 합계가 대상인 후보에서 모든 고유한 조합을 찾습니다.

후보자의 각 번호는 조합에서 한 번만 사용할 수 있습니다.

참고: 솔루션 세트는 중복 조합을 포함하지 않아야 합니다.

다음에서 가져온 문제 설명: https://leetcode.com/problems/combination-sum-ii .

예 1:

Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output:
[
[1, 1, 6],
[1, 2, 5],
[1, 7],
[2, 6]
]

예 2:

Input: candidates = [2, 5, 2, 1, 2], target = 5
Output:
[
[1, 2, 2],
[5]
]

제약:

- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30

설명

역추적

이 문제는 지난번 블로그 [Combination Sum ( https://alkeshghorpade.me/post/leetcode-combination-sum ) 에서 사용한 것과 유사한 접근 방식을 사용하여 해결할 수 있습니다. 유일한 차이점은 후보의 각 요소가 한 번만 사용될 수 있다는 것입니다. 각 요소를 한 번만 사용하면 함수를 재귀적으로 호출할 때 다음 인덱스로 점프하여 얻을 수 있습니다.

또 다른 차이점은 솔루션 세트에 중복 조합이 포함되어서는 안 된다는 것입니다. 문제 설명에는 배열이 정렬되어 있다는 언급이 없습니다. 중복 결과 집합을 피하려면 배열을 정렬하고 동일한 요소를 사용하지 않아야 합니다.

먼저 알고리즘을 확인해 봅시다.

- initialize the result as a 2D array
  initialize current as an array

  // n = index, at start it will be 0.
  // sumTillNow = sum of the current elements in the array, at the start it will be 0
  // current = current list of elements in the array, at the start it will be an empty array []
- call combinationSum2Util(result, candidates, current, n, sumTillNow, target)

- return result

// combinationSum2Util function
- if sumTillNow == target
  // append current to result
  - result.push_back(current)

- if sumTillNow > target
  - return

- set prev = -1

- loop for i = n; i <= candidates.size() - 1; i++
  - if prev != candidates[i]
    // append candidates array ith element to the current array
    - current.push_back(candidates[i])

    - sumTillNow += candidates[i]

    // call the function recursively
    - combinationSumUtil(result, candidates, i, target, sumTillNow, current)

    - sumTillNow -= current[current.size() - 1]

    // remove the last element from the array
    - current.pop_back()

    - prev = candidates[i]
  - end of if

C++, Golang 및 Javascript의 솔루션을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    void combinationSum2Util(vector<vector<int>> &result, vector<int>& candidates, vector<int>& current, int index, int sumTillNow, int target) {
        if(sumTillNow == target) {
            result.push_back(current);
            return;
        }

        if(sumTillNow > target) {
            return;
        }

        int prev = -1;

        for(int i = index; i <= candidates.size() - 1; i++) {
            if(prev != candidates[i]) {
                current.push_back(candidates[i]);
                sumTillNow += candidates[i];

                combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target);
                sumTillNow -= current[current.size() - 1];

                current.pop_back();
                prev = candidates[i];
            }
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current;

        sort(candidates.begin(), candidates.end());
        combinationSum2Util(result, candidates, current, 0, 0, target);
        return result;
    }
};

골랑 솔루션

func combinationSum2Util(result *[][]int, candidates, current []int, index, sumTillNow, target int) {
    if sumTillNow == target {
        *result = append(*result, append([]int{}, current...))
        return
    }

    if sumTillNow > target {
        return
    }

    prev := -1

    for i := index; i < len(candidates); i++ {
        if prev != candidates[i] {
            current = append(current, candidates[i])
            sumTillNow += candidates[i]

            combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
            sumTillNow -= current[len(current) - 1]
            current = current[:len(current) - 1]
            prev = candidates[i]
        }
    }
}

func combinationSum2(candidates []int, target int) [][]int {
    result := make([][]int, 0)

    sort.Ints(candidates)
    combinationSum2Util(&result, candidates, []int{}, 0, 0, target)

    return result
}

자바스크립트 솔루션

var combinationSum2 = function(candidates, target) {
    let result = [];
    candidates.sort(function(a, b){ return a - b });

    const combinationSum2Util = (candidates, current, index, sumTillNow, target) => {
        if( sumTillNow == target ) {
            result.push([...current]);
            return;
        }

        if( sumTillNow > target ) {
           return;
        }

        let prev = -1;

        for(let i = index; i < candidates.length; i++) {
            if(prev != candidates[i]) {
                current.push(candidates[i]);
                sumTillNow += candidates[i];

                combinationSum2Util(candidates, current, i + 1, sumTillNow, target);

                sumTillNow -= current[current.length - 1];
                current.pop();

                prev = candidates[i];
            }
        }
    }

    combinationSum2Util(candidates, [], 0, 0, target);

    return result;
};

알고리즘을 시험 실행해 봅시다.

Input: candidates = [2, 5, 2, 1, 2]
       target = 5

// combinationSum function
Step 1: vector<vector<int>> result
        vector<int> current

Step 2: sort(candidates.begin(), candidates.end()
        [1, 2, 2, 2, 5]

Step 3: combinationSum2Util(result, candidates, current, 0, 0, target)

// combinationSum2Util function
Step 4: if sumTillNow == target
           0 == 5
           false

        if sumTillNow > target
           0 > 5
           false

        prev = -1

        loop for int i = index; i <= candidates.size() - 1
          i = 0
          0 <= 5 - 1
          true

          - if prev != candidates[i]
               -1 != 1
               true

            current.push_back(candidates[i])
            current.push_back(candidates[0])
            current.push_back(1)
            current = [1]

            sumTillNow += candidates[i]
                        = sumTillNow + candidates[0]
                        = 0 + 1
                        = 1

            combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
            combinationSum2Util([][], [1, 2, 2, 2, 5], [1], 1, 1, 5)

Step 5: if sumTillNow == target
           1 == 5
           false

        if sumTillNow > target
           1 > 5
           false

        prev = -1

        loop for int i = index; i <= candidates.size() - 1
          i = 1
          1 <= 5 - 1
          true

          - if prev != candidates[i]
               -1 != 2
               true

            current.push_back(candidates[i])
            current.push_back(candidates[1])
            current.push_back(2)
            current = [1, 2]

            sumTillNow += candidates[i]
                        = sumTillNow + candidates[1]
                        = 1 + 2
                        = 3

            combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
            combinationSum2Util([][], [1, 2, 2, 2, 5], [1, 2], 3, 3, 5)

Step 6: if sumTillNow == target
           3 == 5
           false

        if sumTillNow > target
           3 > 5
           false

        prev = -1

        loop for int i = index; i <= candidates.size() - 1
          i = 2
          2 <= 5 - 1
          true

          - if prev != candidates[i]
               -1 != 2
               true

            current.push_back(candidates[i])
            current.push_back(candidates[1])
            current.push_back(2)
            current = [1, 2, 2]

            sumTillNow += candidates[i]
                        = sumTillNow + candidates[1]
                        = 3 + 2
                        = 5

            combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
            combinationSum2Util([][], [1, 2, 2, 2, 5], [1, 2, 2], 3, 5, 5)

Step 7: if sumTillNow == target
           5 == 5
           true

           result.push_back(current)
           result = [[1, 2, 2]]

           return

           we backtrack to step 6 and continue

Step 8: combinationSumUtil([][], [1, 2, 2, 2, 5], [1, 2, 2], 3, 5, 5)
        sumTillNow = sumTillNow - current[current.size() - 1]
                   = 5 - current[3 - 1]
                   = 5 - current[2]
                   = 5 - 2
                   = 3

        current.pop_back()
        current = [1, 2]

        prev = candidates[i]
             = candidates[2]
             = 2

        i++
        i = 3

        loop for int i = index; i <= candidates.size() - 1
          i = 3
          3 <= 5 - 1
          true

          - if prev != candidates[3]
               2 != 2
               false

        i++
        i = 4

        loop for int i = index; i <= candidates.size() - 1
          i = 3
          4 <= 5 - 1
          true

          - if prev != candidates[4]
               2 != 5
               true

            current.push_back(candidates[i])
            current.push_back(candidates[4])
            current.push_back(5)
            current = [1, 2, 5]

            sumTillNow += candidates[i]
                        = sumTillNow + candidates[4]
                        = 3 + 5
                        = 8

            combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
            combinationSum2Util([][], [1, 2, 2, 2, 5], [5], 5, 8, 5)

Step 9: if sumTillNow == target
           8 == 5
           false

        if sumTillNow > target
           8 > 5
           true
           return

        we backtrack to step 5 and continue

Step 10: combinationSum2Util([][], [1, 2, 2, 2, 5], [1, 2], 3, 3, 5)
         sumTillNow = sumTillNow - current[current.size() - 1]
                   = 3 - current[2 - 1]
                   = 3 - current[1]
                   = 3 - 2
                   = 1

         current.pop_back()
         current = [1]

         prev = candidates[i]
              = candidates[1]
              = 2

         i++
         i = 2

         loop for int i = index; i <= candidates.size() - 1
          i = 2
          2 <= 5 - 1
          true

          - if prev != candidates[3]
               2 != 2
               false

         i++
         i = 3

         loop for int i = index; i <= candidates.size() - 1
          i = 3
          3 <= 5 - 1
          true

          - if prev != candidates[3]
               2 != 2
               false

         i++
         i = 4

         loop for int i = index; i <= candidates.size() - 1
          i = 4
          4 <= 5 - 1
          true

          - if prev != candidates[4]
               2 != 5
               true

            current.push_back(candidates[i])
            current.push_back(candidates[4])
            current.push_back(5)
            current = [1, 5]

            sumTillNow += candidates[i]
                        = sumTillNow + candidates[4]
                        = 1 + 5
                        = 6

            combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
            combinationSum2Util([][], [1, 2, 2, 2, 5], [1, 5], 5, 6, 5)

Step 11: if sumTillNow == target
           6 == 5
           false

         if sumTillNow > target
            6 > 5
            true
            return

         we backtrack to step 4 and continue

We similarly iterate from index 2, backtrack, and then reach the last index.

We return the answer as
[
  [1, 2, 2],
  [5]
]