순열, 중복순열, 조합, 중복조합

순열

function solution(arr, n) {
  let result = []
  function DFS(n, tempArr) {
    if (n === 0) return result.push(tempArr)
    for (let i = 0; i < arr.length; i++) {
      if (!tempArr.includes(arr[i])) DFS(n - 1, tempArr.concat(arr[i]));
    }
  }
  DFS(n, [])
  return result
}

// n만 주어졌을 때
function solution(n) {
  let result = []
  let N = n
  function DFS(n, tempArr) {
    if (n === 0) return result.push(tempArr)
    for (let i = 1; i <= N; i++) {
      if (!tempArr.includes(i)) DFS(n - 1, tempArr.concat(i))
    }
  }
  DFS(n, [])
  return result
}

// 경우의 수만 구하기
function solution(n, r) {
  return factorial(n) / factorial(n - r)
}

 

중복 순열

function solution(arr, n) {
  let result = []
  function DFS(n, tempArr) {
    if (n === 0) return result.push(tempArr)
    for (let i = 0; i < arr.length; i++) {
      DFS(n - 1, tempArr.concat(arr[i]))
    }
  }
  DFS(n, [])
  return result
}

// n만 주어졌을 때
function solution(n) {
  let result = []
  let N = n
  function DFS(n, tempArr) {
    if (n === 0) return result.push(tempArr)
    for (let i = 1; i <= N; i++) {
      DFS(n - 1, tempArr.concat(i))
    }
  }
  DFS(n, [])
  return result
}

더 빠르게 하는법 중복조합 말고 다른애들도 참고

// n과 m이 주어졌을 때    n은 1부터 n까지, m은 몇개 뽑을지
// 이건 push안쓰고 배열의 요소값을 바꾸는거라 2배정도 빠름

function solution(n, m) {
  let result = []
  let tmp = new Array(m).fill(0)
  function DFS(L) {
    if (L === m) result.push(tmp.slice())
    else {
      for (let i = 1; i <= n; i++) {
        tmp[L] = i
        DFS(L + 1)
      }
    }
  }
  DFS(0)
  return result
}

// 경우의 수만 구하기
function solution(n, r) {
  return n ** r
}

 

조합

function solution(arr, n) {
  let result = []
  function combination(n, tempArr, index) {
    if (n === 0) return result.push(tempArr)
    for (let i = index; i < arr.length; i++) {
      combination(n - 1, tempArr.concat(arr[i]), i + 1)
    }
  }
  combination(n, [], 0)
  return result
}

// n만 주어졌을 때
어차피 1개임

// 경우의 수만 구하기
function solution(n, r) {
   return factorial(n) / (factorial(r) * factorial(n - r))
}

 

중복 조합

function solution(arr, n) {
  let result = []
  function combination(n, tempArr, index) {
    if (n === 0) return result.push(tempArr)
    for (let i = index; i < arr.length; i++) {
      combination(n - 1, tempArr.concat(arr[i]), i)
    }
  }
  combination(n, [], 0)
  return result
}

// n만 주어졌을 때
function solution(n) {
  let result = []
  let N = n
  function combination(n, tempArr, index) {
    if (n === 0) return result.push(tempArr)
    for (let i = index; i < N; i++) {
      combination(n - 1, tempArr.concat(i), i)
    }
  }
  combination(n, [], 0)
  return result
}

// 경우의 수만 구하기
function solution(n, r) {
  return factorial(n + r - 1) / (factorial(r) * factorial(n - 1))
}

 

사용한 factorial 함수

function factorial(n) {
  return n ? n * factorial(n - 1) : 1
}