특정 값을 만족하는 조합 구하기(ps.파이썬의 위엄..)

문제

n개의 정수로 이루어진 리스트 nums와 정수 target이 주어졌을 때, num에 있는 정수 4개를 합하여 target을 만들 수 있는 모든 조합을 구하시오.단, 정답에는 동일한 정수 조합이 여러개 포함되어서는 안된다.

 

문제풀이

1. 중복을 허락하지 않기 때문에 이를 확인할 수 있는 체크 배열을 생성
2. 조건을 만족하는 정수 조합은 여러개 포함되면 안되기 때문에 이를 식별할 수 있는 별도의 변수 선언
3. 깊이 탐색을 통해 조건에 만족하는 조합을 정답 리스트에 포함시키고, 처음 재귀를 시작할 때 해당 정답 리스트에 현재 검사하는 조합이 포함되어 있는지 검사_조합은 순서를 고려하지 않기 때문에 하고, 있다면 그대로 함수를 종료

처음에는 3번 조건을 만족시키기 위해 forEach 메서드를 사용하여 순회하려고 했지만 조건을 만족하는 경우를 찾았을 때 forEach는 콜백 함수를 종료시키지 않고 요소 끝까지 순회하면서 원하는 결과값을 얻지 못하는 문제가 발생하였다.

 

forEach 메서드는 기본적으로 break문을 허용하지 않기 때문에 이와 같은 일이 생긴건데 찾아보니 Array.prototype.some 메서드가 있었다.

some() 메서드는 배열 안의 어떤 요소라도 주어진 판별 함수를 통과하는지 테스트합니다.

 

정답 리스트는 2차원 배열이기 때문에 some 메서드를 사용하여 각 요소의 1차원 배열을 순회하도록 하고, 해당 1차원 배열을 filiter 메서드를 사용하여 콜백 함수로 현재 검사하고자 하는 조합 배열 tmp에 대해 includes 메서드로 해당 요소가 있는지 없는지 식별하였다.

 

만약에 현재 검사하고자 하는 조합 배열 tmp의 모든 값이 정답 리스트 내의 조합 중에 하나라도 있다면 includes 메서드에 대해서 모든 리턴 값이 true가 되므로 최종적으로 1차원 배열에서의 filiter 메서드가 반환하는 새로운 배열의 길이는 4(정수 조합)가 될 것이다.

 

그래서 배열의 길이가 4라는 조건을 만족한다면 이후 순회를 더 할 필요 없이 some 메서드는 true를 반환하고 이를 이용하여 3번의 조건을 만족시켰다.

 

코드

function solution(nums, target) {
  let answer = [];
  let tmp = Array.from({ length: 4 });
  let ch = Array.from({ length: nums.length }, () => 0); 
  let ch2 = false;

  function DFS(L) {
    ch2 = answer.some((arr) => arr.filter((x) => tmp.includes(x)).length === 4);
    if (ch2) return;
    if (L === 4) {
      if (tmp.reduce((a, b) => a + b) === target) {
        answer.push([...tmp]);
      }
    } else {
      for (let i = 0; i < nums.length; i++) {
        if (ch[i] === 0) {
          ch[i] = 1;
          tmp[L] = nums[i];
          DFS(L + 1);
          ch[i] = 0;
        }
      }
    }
  }

  DFS(0);
  return answer;
}

let nums = [1, 0, -1, 0, -2, 2];
console.log(solution(nums, 0));

 

파이썬 itertools combinations

JS를 통해 조건에 맞는 조합을 구하기 위해 다소 긴(?) 재귀 함수를 작성하였다.이에  반해 파이썬은 간단하게 조합을 구할 수 있는 별도의 함수인 itertools의 combinations가 있었다.

def solution(nums, target):
	result = [items for items in intertools.combinations(nums, 4) if sum(items) == target]
    return result
    
print(solution[1, 0, -1, 0, -2, 2], 0)

JS에서도 조합을 구하는 더 간단하고 효율적인 방식이 있는지 찾아봐야겠다.

(현재 Array.some 으로 조합의 조건을 만족시키는 방법은 코드 상 복잡하고 정석적인 방법이 아닌 것 같다..)

 

(추가_2021.08.08)

조합 구하기

이전에 조합에 대한 제대로 된 이해 없이 Array.some 메서드를 사용하여 조합의 순서를 고려하지 않는다 라는 조건을 만족시켰는데 이보다 더 간단한 방법이 있었다.

다음 그림을 통해 살펴보자.

조합

 

function solution(n, m) {
  let answer = [];
  let tmp = Array.from({length: m}, () => 0);

  function DFS(L, s) {
    if(L === m) {
      answer.push(tmp.slice())
    }
    else {
      for(let i = s; i <= n; i++) { //다음 재귀에서의 반복문 시작은 1가산
          tmp[L] = i;
          DFS(L + 1, i + 1);
      }
    }
  }
  
  DFS(0, 1);
  return answer;
}

console.log(solution(4, 2));

---

function solution(m, nums) {
  let answer = [];
  let tmp = Array.from({length: m}, () => 0);
  let n = nums.length;

  function DFS(L, s) {
    if(L === m) {
      if(tmp.reduce((a, b) => a +b) % 6 === 0) answer.push(tmp.slice());
    }
    else {
      for(let i = s; i < n; i++) {
        tmp[L] = nums[i];
        DFS(L + 1, i + 1);
      }
    }
  }
  
  DFS(0, 0); //배열의 인덱스를 순회 및 참조해야 되기 때문에 start는 0부터 시작
  return answer;
}

let nums = [2, 4, 5, 8, 12]
console.log(solution(3, nums));