배열 내에서 합을 찾는 알고리즘?

Question

당신은 모든 양수이고 N보다 작은 요소를 가진 배열을 가지고 있다고 가정 해보십시오.

누군가 내에서 일부 하위 집합이 있는지 알고리즘에 대한 일반적인 설명을 제공 할 수 있습니까? 모든 원소가 N에 정확히 합쳐지는 배열?

특별히 효율적 일 필요는 없습니다. 내가 작업하는 세트는 아주 작습니다. 효율성이 중요하지 않은 경우

Answer 1

, 높은 수준의 알고리즘은 다음과 같습니다

input: array A[1..K] of positive numbers, positive N 

    for each subset S of { 1..K } 
     sum = 0 
     for each i in S 
      sum = sum + A[i] 
     end 
     if (sum equals N) return true 
    end 
    return false 

Answer 2

의사 코드는. 매우 비효율적이다. 실제로이 numbers 재귀 호출 (심판에 의해 전달되지 않음)에 복사되어 있는지 확인 구현하는 경우

if empty(numbers) return false 
return hasSumSubset(numbers, N) 

boolean hasSumSubset(numbers[], N): 
    p = pop(numbers) 
    if empty(numbers) return N == p 
    return hasSumSubset(numbers, N-p) or hasSumSubset(numbers, N) 

; 그렇지 않으면 올바르게 작동하지 않습니다.