. 목표합계

494. 목표합계

난이도:중

주제: 배열, 동적 프로그래밍, 역추적

정수 배열 nums와 정수 타겟이 제공됩니다.

nums의 각 정수 앞에 기호 '' 및 '-' 중 하나를 추가한 다음 모든 정수를 연결하여 nums로 식을 작성하려고 합니다.

• 예를 들어 nums = [2, 1]인 경우 2 앞에 ''를 추가하고 1 앞에 '-'를 추가하고 이를 연결하여 " 2-1"이라는 표현식을 작성할 수 있습니다.

생성할 수 있고 대상으로 평가되는 다양한 표현식의 수를 반환합니다.

예 1:

• 입력: 숫자 = [1,1,1,1,1], 대상 = 3
• 출력: 5
• 설명: 숫자의 합이 대상 3이 되도록 기호를 할당하는 방법에는 5가지가 있습니다.
  • -1 1 1 1 1 = 3
  • 1 - 1 1 1 1 = 3
  • 1 1 - 1 1 1 = 3
  • 1 1 1 - 1 1 = 3
  • 1 1 1 1 - 1 = 3

예 2:

• 입력: 숫자 = [1], 대상 = 1
• 출력: 1

제약조건:

• 1 <= nums.length <= 20
• 0 <= 숫자[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= 대상

해결책:

"Target Sum" 문제는 각 숫자에 또는 - 기호를 할당하여 숫자 배열의 숫자를 사용하여 표현식을 만드는 것과 관련됩니다. 목표는 해당 표현식이 주어진 대상으로 평가되는 수를 계산하는 것입니다. 이 문제는 동적 프로그래밍이나 역추적을 사용하여 효율적으로 해결할 수 있습니다.

핵심사항

1. 입력 제약:
   • 배열 길이: 1 <= nums.length <= 20
   • 요소 값: 0 <= nums[i] <= 1000
   • 대상 범위: -1000 <= 대상 <= 1000

2. 출력:

   • 타겟으로 평가되는 표현식의 개수를 반환합니다.

3. 도전과제:

   • 솔루션은 목표의 작은 값과 큰 값을 모두 처리해야 합니다.
   • 역추적 사용 시 최대 2²⁰개의 조합을 효율적으로 처리합니다.

접근방법

이 문제는 동적 프로그래밍(부분합 합 변환) 또는 역추적을 사용하여 해결할 수 있습니다. 아래에서는 효율성을 위해 동적 프로그래밍(DP)을 사용합니다.

주요 관찰:

1. nums를 P(양성 하위 집합)와 N(음성 하위 집합)의 두 그룹으로 나누면 다음과 같습니다. target = sum(P) - sum(N)

항 재배열: sum(P) sum(N) = sum(nums)

S 를 양의 부분 집합의 합으로 둡니다. 그런 다음: S = (합계(숫자) 목표) / 2

1. (sum(nums) target) % 2 ≠ 0인 경우 합계를 분할할 수 없으므로 0을 반환합니다.

계획

1. 숫자의 총합을 계산합니다.
2. S의 공식을 이용해 목표 달성 가능 여부를 확인하세요. 유효하지 않은 경우 0을 반환합니다.
3. DP 접근 방식을 사용하여 합계가 S와 같은 숫자의 하위 집합 수를 찾습니다 .

이 솔루션을 PHP로 구현해 보겠습니다: 494. 목표합계

<?php
/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer
 */
function findTargetSumWays($nums, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [1, 1, 1, 1, 1];
$target = 3;
echo findTargetSumWays($nums, $target); // Output: 5
?>

설명:

1. 입력 유효성 검사:

   • S를 계산합니다 = (sum(nums) target) / 2.
   • S 가 정수가 아닌 경우 숫자를 두 개의 하위 집합으로 분할하는 것은 불가능합니다.

2. 동적 프로그래밍 논리:

   • dp[j]는 주어진 숫자를 사용하여 합 j를 형성하는 방법의 수를 나타냅니다.
   • dp[0] = 1부터 시작하여 nums의 각 숫자에 대해 j - num을 형성하는 방법의 수를 더하여 dp[j]를 업데이트합니다.

3. 결과:

   • 모든 숫자를 처리한 후 dp[S]에는 목표 합계를 달성하는 방법의 개수가 포함됩니다.

예시 연습

입력: nums = [1, 1, 1, 1, 1], 대상 = 3

1. totalSum = 5, S = (5 3) / 2 = 4.
2. DP 배열 초기화: dp = [1, 0, 0, 0, 0].
3. 각 번호 처리:
   • 1의 경우: dp 업데이트: [1, 1, 0, 0, 0].
   • 1의 경우: dp 업데이트: [1, 2, 1, 0, 0].
   • 1의 경우: dp 업데이트: [1, 3, 3, 1, 0].
   • 1의 경우: dp 업데이트: [1, 4, 6, 4, 1]
   • 1의 경우: dp 업데이트: [1, 5, 10, 10, 5].
4. 결과: dp[4] = 5.

시간복잡도

• 시간: O(n x S), 여기서 n은 숫자의 길이이고 S는 목표 합계입니다.
• Space: DP 배열의 경우 O(S)

예시 출력

입력: 숫자 = [1,1,1,1,1], 대상 = 3

출력: 5

이 접근 방식은 동적 프로그래밍을 사용하여 목표 합계를 구성하는 방법의 수를 효율적으로 계산합니다. 문제를 부분 집합 합계로 줄임으로써 더 나은 성능을 위해 DP 구조를 활용합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 목표합계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!