조합 합계 | 백트래킹

출처: Dev.to leetcode.com

distinct 정수 candidates 배열과 target 값을 주어, 합이 target이 되는 모든 고유한 조합을 반환합니다. 숫자는 무제한으로 선택할 수 있습니다. 각 원소에 대해 두 가지 선택이 있습니다:

• 선택한다

• 스킵한다 요소를 선택하면 다시 선택할 수 있습니다. 반복이 허용됩니다. 모든 가능한 조합을 계속 탐색합니다. 다음 조건에서 멈춥니다:

• target이 0이면 → 유효한 조합

• target이 음수가 되면 → 무효 경로 다음과 같은 경우를 보게 됩니다:

• 모든 가능한 조합을 생성한다

• 목표 합

• 요소의 무제한 사용 생각해 보세요:

• 백트래킹 + 선택/스킵

• 선택 후 동일한 인덱스 유지 왜? 같은 요소를 여러 번 사용할 수 있기 때문입니다. 예시: candidates = [2,3,6,7] target = 7 형성할 수 있는: [2,2,3] 2를 반복해서 선택할 수 있어야 합니다. import java.util.*; class Solution { public List<List> combinationSum(int[] candidates, int target) {

    List<List<Integer>> ans = new ArrayList<>();
  
    helper(0, candidates, target, ans, new ArrayList<>());
  
    return ans;

  }

  private void helper(int index, int[] candidates, int target, List<List> ans, List ds) {

    if (target == 0) {
        ans.add(new ArrayList<>(ds));
        return;
    }
  
    if (index == candidates.length) {
        return;
    }

// 선택 if (candidates[index] 백트래킹 => 선택 / 스킵 => 선택 후 동일한 인덱스 유지 조합 합 코인 챈지 (방법 생성) 무제한 배낭 로드 커팅 정수 분해