인프런 커뮤니티 질문&답변

안녕하세요 이번 강의를 듣고 선생님께서 알려주신 풀이 방법을 이해하게 되었습니다 감사합니다!

다만 제가 몇가지 질문이 있어 글 올립니다!

1 . 풀이 방향이 각각의 (조합) * (숫자) 의 합이 되는데 왜 마지막 숫자가 (조합) * (숫자) 의 합이 되나요 ???

2. 제가 강의를 듣기전에 혼자서 코드를 짜보았는데 왜 이 코드는 답이 안나오는지 여쭈고 싶습니다!

function solution(n, end) {
  let mem_arr = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); // 메모이제이션
  let comb_arr = Array.from({ length: n }, () => 0); // 조합의 배열

  let check = Array.from({ length: n }, () => false); // for 수열 (중복X)
  let arr = Array.from({ length: n }, () => 0); // 순열 저장

  let answer = [];

  function comb(n, r) {
    if (n === r || r === 0) return (mem_arr[n][r] = 1);
    if (mem_arr > 0) return mem_arr[n][r];
    return (mem_arr[n][r] = comb(n - 1, r - 1) + comb(n - 1, r));
  }

  for (let i = 0; i < n; i++) {
    comb_arr[i] = comb(n - 1, i);
  }
  function dfs(lev) {
    if (lev >= n) {
      let sum = 0;
      for (let i = 0; i < n; i++) {
        sum += comb_arr[i] * (i + 1);
      }
      if (sum === end) {
        answer.push(arr.slice());
      }
    } else {
      for (let i = 1; i <= n; i++) {
        if (check[i] === true) continue;
        check[i] = true;
        arr[lev] = i;
        dfs(lev + 1);
        check[i] = false;
      }
    }
  }
  dfs(0);

  return answer;
}

제가 처음에 의도했던 코드의 경우로는,,

일단 순열을 arr에 저장하고 lev=== n 이 될때 구한 순열과 조합의 곱의 합인 sum 을 구하여 비교하는 방식으로 짰습니다.

근데 이 코드를 실행해보니까 arr 이 (1,2,3,4) 로만 나오는데 어디서 잘못됐는지 잘 모르겠습니다!!

답변 주시면 정말 감사하겠습니다 😄