[알고리즘] 부분 집합 모두 찾기

하나의 집합을 의미하는 문자열을 입력받아 각 문자를 가지고 만들 수 있는 모든 부분집합을 리턴해야 하는 문제.

PowerSet 함수에 인자로 들어오는 str은 공백이 없는 알파벳 소문자 문자열이고, 해당 문자열의 부분집합인 문자열들을 요소로 가지는 배열을 반환해야 한다. 부분집합 배열에는 맨 처음에 빈 문자열을 가져야 하고, 문자열 알파벳 순서로 정렬되어야 한다.

//예시 

powerSet('abc');//['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']

계속해서 부분집합을 만들어내야 하기 때문에 재귀를 사용해야 한다. makeSubset이라는 재귀 함수를 만들어서 사용할 것이다.그리고 str의 각 문자들이 부분집합 문자열을 만드는 데 사용이 되었는지 여부를 저장하는 객체가 필요하다.

재귀 탈출 조건은 문자열에 있는 알파벳을 모두 다 넣었을 때, 부분집합 문자열의 길이가 인자 str의 길이와 동일할 때이다.

const powerSet = function (str) {
let result = [""]; //부분집합 문자열들을 담을 배열 : 빈문자열은 미리 집어넣어놓기
  let subset = ""; //만들어진 부분집합 문자열 
  let check = {};//사용 여부 체크하는 객체 
  
  //재귀 함수
  //jump라는 문자열을 받았다고 가정해보면 
  function makeSubset() {
    //탈출조건: 문자열에 있는 알파벳 모두 다 넣었을 때
    if (subset.length >= str.length) {
      return;
    }
  	
    for (let i = 0; i < str.length; i++) {
      if (!check[str[i]]) {
        //아직 subset에 안들어간 알파벳이면 str[i]가 한글자씩 들어감
        subset += str[i]; //합치고
        check[str[i]] = true;//str[i]가 들어갔다고 표시함.
        let sortSubset = subset.split("").sort().join("");
        //부분집합의 문자들은 알파벳 순서로 정렬되어야 하므로 
        //부분집합 문자열을 분리해서 배열로 만들어서 정렬하고, 다시 붙여서 문자열로 만듦.
        if (result.indexOf(sortSubset) === -1) {
          //check 배열로는 만들어지는 부분집합 문자열 속에서 알파벳 중복을 막아 준 것이고 이 코드는 jmup와 jpum 같은 중복을 없애기 위한 것이다.
          result.push(sortSubset);
        }
        makeSubset(); //재귀 함수 호출해서 아직 안 들어간 알파벳을 새로 붙여서 탈출조건(모든 문자 다 사용)에 맞을 때까지 계속해서 문자를 덧붙여준다. 
        //재귀를 이용하기 때문에 차례로 j, ju, jmu, jmpu 순으로 만들어진 문자열이 result 속으로 들어간다. 
        //모든 문자를 다 사용해서 탈출조건을 충족해서 빠져 나오면 현재 subset은  "jmpu"이고 i = 4이다.
        subset = subset.slice(0, -1);
        //그리고 위 코드를 통해 subset은 jmp로 바뀐다.
        //즉 순서대로 넣어주고 다시 뒤로 돌아가서 처음부터 중복제거해서 넣어주는 걸 반복한다고 생각하면 된다.
        check[str[i]] = false;
        //subset에서 제거되었으므로 check도 false로 초기화 
      }
    }
  }
  makeSubset();
  return result.sort();
};

makeSubset 함수 속 반복문은 str에 "jump"를 인자로 받았을 때 j, u, m, p로 시작하는 문자열을 만드는 각각의 과정을 운영한다.

중요한 점은 부분집합은 정렬되어야 하므로 사실 알파벳의 순서는 상관없이 알파벳이 부분집합에 동일하게 쓰였다면 동일한 부분집합이라는 점이다.

'abc'와 'bca'는 동일한 부분집합이고, 그를 판결하는 것이 let sortSubset = subset.split("").sort().join("")이다.

재귀 탈출조건을 통해 탈출한 경우 slice로 맨 뒤의 글자를 제거해주는데, 이렇게 제거해주면서 다른 경우의 수들을 찾아나간다.(사실 이 부분이 아직 제대로 이해가 안 되어서 조금 더 생각해보고 추가해야겠다.)

다른 풀이법을 찾아보다 여기에서 DFS로 푸는 풀이도 찾았다.