Portfolio

📄문제

✏️풀이

재영

일단 새로 배열 만드는 거 자체가 메모리 낭비 → 그냥 for문 해씀니다.

맨 뒤부터 시작함니다.

i = n부터 시작 → 1씩 감소됨니다.

앞부분을 만들기 위해 재귀 실행 → k보다 작으면 조합을 만들 수 없음 → 가지치기함니다.

만약 k = 1이 되면 → 가능한 경우의 수를 배열로 만듬니다.

그러면 결과적으로 k=1, k=2, ...로 쭉 들어가서 계산이 됨. 결과적으로 k=2일 때에는 k=1인 배열의 모음에 현재 자신을 더해준 배열로 만들어주면 됨니다.

이를 반복하다 보면 조합 결과를 만들 수 이씀니다.


const combine = (n, k) => {
	// 조건: 만약 n보다 k가 작으면 가지치기.
  if (n < k) return [];

	// 만약 k가 1일 때 모든 배열 값들을 2차원 배열로 만든 값 반환
  if (k === 1) return Array.from({length: n}, (_, idx) => [idx + 1]);

	// 결과 값은 여기에 담는다.
  let result = [];

	// for문을 돌린다. 이때, i가 0보다 클 때까지만 순회시킨다.
  for(let i = n; i > 0; i -= 1) {
		// 재귀를 통해 반환되는 값은 result이다.
		// 만약 i = 3, k === 1일 때, [[1],[2],[3]]가 반환됐다고 하자.
		// 그러면 [[4, 1], [4, 2], [4, 3]]으로 넣어주는 것이다.
		// 만약 i = 2, k === 1일 때, [[1],[2]]일 거고,
		// 그러면 [[3, 2], [3, 1]]이 반환된다.
    combine(i - 1, k - 1)
    .forEach(comb => {
      result.push([i, ...comb])
    })
  }
	// 결과적으로 현재 `combine`의 결과값을 반환한다.
  return result;
}

// 112ms

효성


function combine(n, k) {
    const combinations = [];
    const comb = [];
    const nums = [...Array(n)].map((_, idx) => idx+1);
    
    function updateCombinations(pivot) {
        if(k === comb.length) {
           combinations.push([...comb]);
           return;
        }
        
        for(let i = pivot; i < nums.length; i++) {
            if(comb.length > 0 && comb[comb.length-1] >= nums[i]) {
                break;
            }
            comb.push(nums[i]);
            updateCombinations(pivot+1);
            comb.pop();
            
        }
    }
    updateCombinations(0);
    return combinations;
};

은찬


const combination = (arr, count) => {
    const result = [];
    
    if(count === 1){
        return arr.map((val) => [val]);
    }
    
    arr.forEach((fixed, index, origin) => {
        const rest = origin.slice(index + 1);
        const cb = combination(rest, count - 1);
        const attached = cb.map((c) => [fixed, ...c]);
        
        result.push(...attached);
    });
    
    return result;
}

const combine = (n, k) => {
    const array = [];
    
    for(let i = 1; i <= n; i++){
        array.push(i);
    }
    
    return combination(array, k);
};

현석


var combine = function(n, k) {
    const isVisited = new Array(n + 1).fill(false);
    const combination = [];
    const result = [];
    
    const recursion = (index, count) => {
        if (count === k) {
            result.push([...combination])
            return;
        }
        
        for (let i = index; i <= n; i++) {
            if (isVisited[i]) continue;
            isVisited[i] = true;
            combination.push(i);
            recursion(i + 1, count + 1);
            combination.pop()
            isVisited[i] = false
        }
    }
    recursion(1, 0)
    return result
};

태중


var combine = function(n, k) {
  let answer = []
  let tempArray = Array.from({length:k}, ()=>0)

  function DFS(depth, num){
    if(depth===k){
      answer.push(tempArray.slice())
			return
    } 
    for(let i=num; i<=n; i++){
      tempArray[depth] = i
      DFS(depth+1, i+1)
	  }
  }
  DFS(0, 1)
  return answer
};

지난번 순열풀이와 비슷한 DFS 풀이입니다.

depth가 깊어질 때 마다 tempArray의 인덱스를 +1 하면서

tempArray의 값을 수정하고, 목표 depth에 도달하면 answer에 push합니다.