leetcode 39. 조합 총화 40. 조합 총화 II

39. 조합 총화
중복 요소 가 없 는 배열 candidates 와 목표 수 target 을 지정 하여 candidates 의 모든 숫자 와 target 의 조합 을 찾 습 니 다.
candidates 의 숫자 는 무제 한 중복 으로 선택 할 수 있 습 니 다.
설명:
모든 숫자 (target 포함) 는 정수 입 니 다.해 집 은 중복 되 는 조합 을 포함 할 수 없습니다.

   1：

  ：candidates = [2,3,6,7], target = 7,
     ：
[
  [7],
  [2,2,3]
]

tmpPath 는 현재 배열 이 고 target 은 남 은 목표 수량 이 며 start 는 현재 시작 위치 입 니 다.목표 수가 마이너스 라면 과 다 한 무효 임 을 설명 합 니 다.목표 수가 0 이면 현재 배열 을 답 에 추가 합 니 다.목표 수 는 계속 재 귀 하 는 것 이다.주의 하 세 요. 모든 수 를 몇 번 사용 할 수 있 기 때문에 시작 할 때마다 아래 표 시 는 지난번 재 귀 결과 입 니 다.

var combinationSum = function(candidates, target) {
    let n = candidates.length,
        res = [],
        tmpPath = [],
        backtrack = (tmpPath, target, start) => {
            if (target < 0) {
                return;
            }
            if (target == 0) {
                res.push(tmpPath);
                return;
            }
            for (let i = start; i < n; i++) {
                tmpPath.push(candidates[i]);
                backtrack(tmpPath.slice(), target - candidates[i], i);
                tmpPath.pop();
            }
        }
    backtrack(tmpPath, target, 0);
    return res;
};

40. 조합 총화 II
하나의 배열 candidates 와 하나의 목표 수 target 을 지정 하여 candidates 의 모든 숫자 와 target 의 조합 을 찾 습 니 다.
candidates 의 모든 숫자 는 조합 에서 한 번 만 사용 할 수 있 습 니 다.
설명:
모든 숫자 (목표 수 포함) 는 정수 이다.해 집 은 중복 되 는 조합 을 포함 할 수 없습니다.

   1:

  : candidates = [10,1,2,7,6,1,5], target = 8,
     :
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

조건 은 같은 수 를 중복 사용 할 수 없 게 되 었 다.따라서 정렬 을 먼저 하고 매번 교체 할 때마다 start + 1 부터 중복 을 방지 해 야 한다.두 번 째 는 중복 되 는 조합 이 발생 하 는 것 을 방지 하기 위해 tmpPath 0 시 배열 이 기록 되 어 있 으 며, 중복 이 있 으 면 이 조합 이 이미 존재 한 다 는 것 을 설명 하고 바로 건 너 뜁 니 다.

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    candidates.sort((a,b)=>a-b)
    let m = new Map(),
        n = candidates.length,
        res = [],
        tmpPath = [],
        backtrack = (tmpPath, target, start) => {
            if (target < 0) {
                return;
            }
            if (target == 0) {
                res.push(tmpPath);
                return;
            }
            for (let i = start + 1; i < n; i++) {
                tmpPath.push(candidates[i]);
                if(m.has(tmpPath.toString())){
                    // do nothing
                }
                else{
                    m.set(tmpPath.toString(),true);
                    backtrack(tmpPath.slice(), target - candidates[i], i);
                }
                tmpPath.pop();
            }
        }
    backtrack(tmpPath, target, -1);
    return res;
};