LeetCode - 조합 합계 IV

문제 설명

개별 정수 nums의 배열과 대상 정수 대상이 주어지면 대상에 추가되는 가능한 조합의 수를 반환합니다.

답이 32비트 정수에 맞도록 테스트 케이스가 생성됩니다.

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

예 1:

Input: nums = [1, 2, 3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

예 2:

Input: nums = [9], target = 3
Output: 0

제약:

- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- All the elements of nums are unique
- 1 <= target <= 1000

후속 조치: 주어진 배열에 음수가 허용되면 어떻게 됩니까? 문제를 어떻게 바꾸나요? 음수를 허용하려면 질문에 어떤 제한을 추가해야 합니까?

설명

역추적

문제는 이전 블로그 [Combination Sum ( https://alkeshghorpade.me/post/leetcode-combination-sum ) 에서 사용한 것과 유사한 접근 방식을 사용하여 해결할 수 있습니다. 솔루션은 목표에 합산되는 모든 가능한 조합을 생성합니다. 그런 다음 이러한 모든 조합의 수를 반환합니다.

문제는 총 개수만 반환할 것으로 예상하며 동적 프로그래밍을 사용하여 조합 생성을 건너뛸 수 있습니다.

동적 프로그래밍

아래 트리를 확인하고 해결책을 찾아봅시다.



가능한 모든 조합을 생성하고 나머지 목표가 0인지 0보다 작은지 확인합니다. 나머지 목표가 0이면 카운트를 증가시킵니다. 0보다 작으면 반환합니다.

위 논리에 대한 C++ 스니펫은 다음과 같습니다.

int combinationSum4(vector<int>& nums, int target) {
    if (target <= 0) {
        return target == 0 ? 1 : 0;
    }

    int count = 0;

    for (int& num : nums) {
        count += combinationSum4(nums, target - num);
    }

    return count;
}

중복 하위 문제가 많기 때문에 중복 하위 문제 솔루션이 결과 배열에 저장되는 동적 프로그래밍을 적용할 수 있습니다.

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

- initialize result array of size target + 1

// If the target is zero, then there is a combination
- set result[0] = 1

// loop for each target
- loop for t = 1; t <= target; t++

  // for each target, check if there is a combination with all the input nums
  - inner loop for num in nums

    // skip the numbers if they are greater than current target t
    - if t >= num

      // add the combinations that we need for the remaining target
      - result[t] = result[t] + result[t - num]

- return result[target]

C++, Golang 및 Javascript에서 솔루션을 확인합시다.

C++ 솔루션

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> result(target + 1, 0);

        result[0] = 1;

        for(int t = 1; t <= target; t++) {
            for(int &num : nums) {
                if(t >= num) {
                    result[t] += result[t - num];
                }
            }
        }

        return result[target];
    }
};

골랑 솔루션

func combinationSum4(nums []int, target int) int {
    result := make([]int, target + 1)

    result[0] = 1

    for t := 1; t <= target; t++ {
        for _, num := range nums {
            if t >= num {
                result[t] += result[t - num]
            }
        }
    }

    return result[target]
}

자바스크립트 솔루션

var combinationSum4 = function(nums, target) {
    let result = Array(target + 1).fill(0);

    result[0] = 1;

    for(let t = 1; t <= target; t++) {
        for(let i = 0; i < nums.length; i++) {
            if(t >= nums[i]) {
                result[t] += result[t - nums[i]];
            }
        }
    }

    return result[target];
};

주어진 입력에 대해 알고리즘을 연습해 봅시다.

Input: nums = [1, 2, 3]
       target = 4

Step 1: vector<unsigned int> result(target + 1, 0)
        result = [0, 0, 0, 0, 0]

Step 2: result[0] = 1
        result = [1, 0, 0, 0, 0]

Step 3: loop for i = 1; i <= target
            1 <= 4
            true

          loop for int &num : nums
            num = 1

            if t >= num
               1 >= 1
               true

               result[t] = result[t] + result[t - num]
               result[1] = result[1] + result[1 - 1]
                         = 0 + 1
                         = 1

            num = 2

            if t >= num
               1 >= 2
               false

            num = 3

            if t >= num
               1 >= 3
               false

        i++
        i = 2

Step 4: loop for t <= target
          2 <= 4
          true

          loop for int &num : nums
            num = 1

            if t >= num
               2 >= 1
               true

               result[t] = result[t] + result[t - num]
               result[2] = result[2] + result[2 - 1]
                         = 0 + 1
                         = 1

            num = 2

            if t >= num
               2 >= 2
               true

               result[t] = result[t] + result[t - num]
               result[2] = result[2] + result[2 - 2]
                         = 1 + 1
                         = 2

            num = 3

            if t >= num
               2 >= 3
               false

        i++
        i = 3

Step 5: loop for t <= target
          3 <= 4
          true

          loop for int &num : nums
            num = 1

            if t >= num
               3 >= 1
               true

               result[t] = result[t] + result[t - num]
               result[3] = result[3] + result[3 - 1]
                         = 0 + 2
                         = 2

            if t >= num
               3 >= 2
               true

               result[t] = result[t] + result[t - num]
               result[3] = result[3] + result[3 - 2]
                         = 2 + 1
                         = 3

            if t >= num
               3 >= 3
               true

               result[t] = result[t] + result[t - num]
               result[3] = result[3] + result[3 - 3]
                         = 3 + 1
                         = 4

        i++
        i = 4

Step 6: loop for t <= target
          4 <= 4
          true

          loop for int &num : nums
            num = 1

            if t >= num
               4 >= 1
               true

               result[t] = result[t] + result[t - num]
               result[4] = result[4] + result[4 - 1]
                         = 0 + 4
                         = 4

            if t >= num
               4 >= 2
               true

               result[t] = result[t] + result[t - num]
               result[4] = result[4] + result[4 - 2]
                         = 4 + 2
                         = 6

            if t >= num
               4 >= 3
               true

               result[t] = result[t] + result[t - num]
               result[4] = result[4] + result[4 - 3]
                         = 6 + 1
                         = 7

        i++
        i = 5

Step 7: loop for t <= target
          5 <= 4
          false

Step 8: return result[target]
               result[4]

We return the answer as 7.