모든 경우의 수 찾기

특정 문자열을 입력받아 모든 경우의 수를 찾으려고 할 때,

이진수를 이용하여 쉽게 출력할 수 있다.

 

1. 문자열을 입력받아 모든 경우의 수를 도출(중복 허용 X)

ex) 'abc'를 입력받으면

'a' 

'ab'

'ac'

'abc'

'b'

'bc'

'c'

 

위와 같이 7개의 경우의 수를 갖는다.

위의 부분집합들을 자릿수(알파벳 순서)에 따라 이진수로 표현해보면

 

'a' -> 1 0 0 

'b' -> 0 1 0 

'c' -> 0 0 1

'ab' -> 1 1 0

 

과 같이 표현 가능하다.

이를 처음에 나열한 모든 경우의 수에 대해서 도출하면 결국 001(2)~111(2)까지 나열한것과 동일하다.

 

이를 이용하여 아래와 같이 코드를 만들 수 있다.

 //elemSet = ['a','b','c']
 for(let i = 0; i < 2**elemSet.length; i++){
 // 이진수로 변환
    binary = i.toString(2);
 // diff를 계산하는 이유는 1(2), 10(2)과 같이 앞부분 인덱스가 비는 경우 001(2), 010(2)와 같은 모양으로 채워주기 위함
    let diff = elemSet.length - binary.length;
    binSet = [...binary]
    if(diff > 0) {
      for(let q = 0; q < diff; q++) {
        binSet.unshift('0');
      }
  }
  //결과 배열에 문자열 합치기(+)
  resultArr[i] = "";
    for(let j = 0; j < elemSet.length; j++){
      if(binSet[j] === '1'){
        resultArr[i] += elemSet[j];
      }
    }
}