[40] Combination Sum II (푸는 중)

주어진 문제

 

주어진 candidates에서 합계가 target인 candidates 조합을 찾는 문제

 

처음에 보자마자 딱 떠오른 생각은

1. candidates의 모든 부분집합을 구한 뒤
2. 누적합이 target이 되는 부분집합을 찾자

그래서 다음과 같이 코드를 작성했다.

const getSubSets = function(arr) {
  const result = [];
  
  const dfs = (start = 0, subset = []) => {
    result.push(subset);
    
    for(let i=start; i<arr.length; i++){

        dfs(i + 1, [...subset, arr[i]]);
    }
  };
  
  dfs();
  
  return result;
}

var combinationSum2 = function(candidates, target) {
    let filteredCandis = candidates.filter((candi) => candi <= target);
    let subSets = [];

    subSets = getSubSets(filteredCandis);

    let result = [];

    subSets.forEach((set) => {
        if (set.reduce((acc, num) => acc + num, 0) === target)
            result.push(set);
    })

    return result;
};

 

하지만 이 코드의 문제점은 getSubSets에서 중복된 부분집합이 나타난다는 것이다.

입력이 위 사진과 같았을 때

아래와 같은 결과가 나온다.

 

어? 왜 이러지? 분명 같은 원소를 다시 집어넣은건 아닌데? 하

 

다시 한번 문제를 읽어보다가, 원래 배열인 candidates에 중복된 값이 포함되어있음을 인지하게 되었다.

다른 인덱스이나, 결국은 같은 값이기에 결과적으로는 중복된 부분집합이 생긴 것이였다.

 

이를 해결하기 위해

const getSubSets = function(arr) {
  const result = [];
  
  const dfs = (start = 0, subset = []) => {
    result.push(subset);
    
    for(let i=start; i<arr.length; i++){
        //중복된 값을 건너뛰기 위한 조건 추가
        if (i > start && arr[i] === arr[i - 1]) continue;
        dfs(i + 1, [...subset, arr[i]]);
    }
  };
  
  dfs();
  
  return result;
}

var combinationSum2 = function(candidates, target) {
    //candidates 배열을 정렬하여 중복요소를 인접하게 위치
    let filteredCandis = candidates.filter((candi) => candi <= target).sort((a, b) => a - b);
    let subSets = [];

    subSets = getSubSets(filteredCandis);
    console.log(subSets);
    let result = [];

    subSets.forEach((set) => {
        if (set.reduce((acc, num) => acc + num, 0) === target)
            result.push(set);
    })

    return result;
};

 

candidates 배열을 정렬할 때 중복요소를 인접하게 위치한 후, dfs에서 이 전 인덱스 값과 비교하여 동일하다면 넘기는 조건을 추가해주었다.

 

하지만 결과는 시간초과

 

Constraints 에서 candidates의 최대 길이가 100이라고 주어졌을 때 솔직히 시간초과 뜰 것 같았는데 아니나 다를까..

 

이렇게되면 그냥 배열 자체에서 하나하나 더해가면서 합이 target이 되었을 때, result에 추가해주는 방법 밖엔 없을거 같다.

 

처음부터 filter로 target보다 큰 원소와, 중복된 원소는 다 빼버리고

거기서 backtracking하면 될 것 같은데.. backtracking 문제를 많이 푼 적이 없어서 고민을 좀 해야할 것 같다.