TIL_201006(재귀적 알고리즘)

 

 

 

부분집합 (Subset)

function solution(arr) {
  let result = [];
  
  function search(index=0, subset=[]) {
    if (index === arr.length) {
    
      // 인덱스 값이 배열 길이 값과 같은 경우 종료
      result.push([...subset]);
      return
      
    } else {
      
      // 현재 인덱스의 요소를 부분 집합에 포함
      subset.push(arr[index]);
      search(index + 1, subset);
      
      // 현재 인덱스의 요소를 부분 집합에 포함하지 않음
      subset.pop();
      search(index + 1, subset);
    }
  }
  
  search();
  return result;
}

 

 

순열 (permutation)

function solution(arr) {
  let result = [];
  
  function search(perArr=[], recordIndex=[]) {
    if (numberArr.length === perArr.length) {
    
      // 크기가 충족되면 종료
      result.push([...perArr]);
      return
      
    } else {
      for (let i = 0; i < numberArr.length; i++) {
      
      	// 이미 값이 들어갔다면 제외
        if (recordIndex[i]) continue;

        // 현재 인덱스의 값을 포함하는 경우
        perArr.push(numberArr[i]);
        recordIndex[i] = true;
        search(perArr, record);

        // 현재 인덱스의 값을 포함하지 않는 경우
        perArr.pop();
        recordIndex[i] = false;
      }
    }
  }
  
  search();
  return result;
}

 

 

주어진 배열의 요소로 만들 수 있는 모든 조합

function solution(arr) {
  let result = [];
  
  function search(n, perArr=[], recordIndex=[]) {
    if (perArr.length === n) {
    
      // 크기가 충족되면 종료
      result.push([...perArr]);
      return
      
    } else {
      for (let i = 0; i < numberArr.length; i++) {
      
      	// 이미 값이 들어갔다면 제외
        if (recordIndex[i]) continue;

        // 현재 인덱스의 값을 포함하는 경우
        perArr.push(numberArr[i]);
        recordIndex[i] = true;
        search(n, perArr, record);

        // 현재 인덱스의 값을 포함하지 않는 경우
        perArr.pop();
        recordIndex[i] = false;
      }
    }
  }
  
  for (let k = 1; k < arr.length; k++) {
    search(k);
  }

  return result;
}

좀 더 효율적인 방법이 없을지 생각해봐야겠습니다.