배열 요소의 합이 특정 값인 조합 찾기

06 Nov 2023

javascript

주어진 배열에서 요소들의 합이 특정한 값을 가지는 조합을 찾는 알고리즘을 구현할 수 있습니다. 이러한 문제는 주어진 숫자들 사이에서 조합을 찾는 것이므로, 조합을 찾는 방법인 조합탐색(Combination Search) 알고리즘을 활용할 수 있습니다.

알고리즘 설명

주어진 배열을 정렬합니다. (오름차순 또는 내림차순)
배열의 각 요소를 순회하면서, 현재 요소부터 시작하여 다른 요소들과의 조합을 탐색합니다. (재귀 또는 반복문)
조합을 탐색할 때, 이미 선택한 요소들의 합과 현재 선택한 요소의 합이 특정 값과 일치하는지 확인합니다.
조합이 일치하는 경우, 해당 조합을 결과로 반환하거나 출력합니다.
배열의 모든 요소에 대해 조합탐색을 완료합니다.

예시 코드 (Python)

def find_combinations(arr, target_sum, current_sum, start, combination, result):
    if current_sum == target_sum:
        # 조합이 일치하는 경우, 결과에 추가
        result.append(combination[:])
        return

    for i in range(start, len(arr)):
        if current_sum + arr[i] > target_sum:
            # 현재 요소를 선택하여 합이 초과하는 경우, 종료
            break

        # 현재 요소 선택
        combination.append(arr[i])

        # 다음 요소로 재귀 호출
        find_combinations(arr, target_sum, current_sum + arr[i], i+1, combination, result)

        # 현재 요소 제거 (백트래킹)
        combination.pop()

def find_combinations_with_target_sum(arr, target_sum):
    # 배열 정렬
    arr.sort()

    # 결과를 저장할 리스트
    result = []

    # 조합탐색 알고리즘 호출
    find_combinations(arr, target_sum, 0, 0, [], result)

    return result

사용 예시

arr = [2, 4, 6, 3, 7]
target_sum = 10

combinations = find_combinations_with_target_sum(arr, target_sum)

print(combinations)  # [[3, 7], [4, 6]]

위의 예시 코드에서는 주어진 배열 [2, 4, 6, 3, 7]에서 요소들의 합이 10이 되는 조합을 찾습니다. 결과로는 [3, 7]과 [4, 6]이 반환됩니다.

참고 문헌

Combination Search