순열과 조합

Key Point

중복 허용 X : 방문 처리 필요 (visit 배열 사용)

순서 상관 X : 인덱스 필요

• 순서 상관 X 라면 AB = BA이다. 따라서 [1, 2], [2, 1]은 같기 때문에 제거 해 주어야 하기 때문에 인덱스가 필요하다.
• 순서 상관 O 라면 AB ≠ BA이다. 따라서 [1, 2], [2, 1]은 2개로 카운트 되기 때문에 인덱스가 필요 없이 모든 경우의 수를 세 주면 된다.

조합 (Combintaion)

• 순서에 상관 없이 n개중 r개를 뽑는다.
• 중복 허용 X, 순서 상관 X

  void combination(vector<int>&candidates, vector <int>&num, int idx, int cnt) {
  if(candidates.size() == cnt) {
    print(candidates);
    return;
  }
  
  for(int i=idx; i<num.size(); i++) {
    if(!visit[i]) {
      visit[i] = 1;
      candidates.push_back(num[i]);
      combination(candidates, num, i+1, cnt);
      candidates.pop_back();
      visit[i] = 0;
    }
  }
  }
  

  // result
  1 2 3 
  1 2 4 
  1 3 4 
  2 3 4 
  

순열 (Permutation)

• 순서에 상관 있이 n개중 r개를 뽑는다.
• 중복 허용 X, 순서 상관 O

  void permutation(vector<int>&candidates, vector <int>&num, int cnt) { // 조합
  if(candidates.size() == cnt) {
    print(candidates);
    return;
  }
  
  for(int i=0; i<num.size(); i++) {
    if(!visit[i]) {
      visit[i] = 1;
      candidates.push_back(num[i]);
      permutation(candidates, num, cnt);
      candidates.pop_back();
      visit[i] = 0;
    }
  }
  }
  

  //result
  1 2 3 
  1 2 4 
  1 3 2 
  1 3 4 
  1 4 2 
  1 4 3 
  2 1 3 
  2 1 4 
  2 3 1 
  2 3 4 
  2 4 1 
  2 4 3 
  3 1 2 
  3 1 4 
  3 2 1 
  3 2 4 
  3 4 1 
  3 4 2 
  4 1 2 
  4 1 3 
  4 2 1 
  4 2 3 
  4 3 1 
  4 3 2 
  

중복 조합

• 조합에서 중복을 허용한다.
• 중복 허용 O, 순서 상관 X

  void duplicate_combination(vector<int>&candidates, vector <int>&num, int idx, int cnt) {
    
  if(candidates.size() == cnt) {
    print(candidates);
    return;
  }
  
  for(int i=idx; i<num.size(); i++) {
    candidates.push_back(num[i]);
    duplicate_combination(candidates, num, i, cnt);
    candidates.pop_back();
  }
  }
  

  //result
  1 1 1 
  1 1 2 
  1 1 3 
  1 1 4 
  1 2 2 
  1 2 3 
  1 2 4 
  1 3 3 
  1 3 4 
  1 4 4 
  2 2 2 
  2 2 3 
  2 2 4 
  2 3 3 
  2 3 4 
  2 4 4 
  3 3 3 
  3 3 4 
  3 4 4 
  4 4 4
  

중복 순열

• 순열에서 중복을 허용한다.
• 중복 허용 O, 순서 상관 O

  void duplicate_permutation(vector<int>&candidates, vector <int>&num, int cnt) {
    
  if(candidates.size() == cnt) {
    print(candidates);
    return;
  }
  
  for(int i=0; i<num.size(); i++) {
    candidates.push_back(num[i]);
    duplicate_permutation(candidates, num, cnt);
    candidates.pop_back();
  }
  }
  

  //result
  1 1 1 
  1 1 2 
  1 1 3 
  1 1 4 
  1 2 1 
  1 2 2 
  1 2 3 
  1 2 4 
  1 3 1 
  1 3 2 
  1 3 3 
  1 3 4 
  1 4 1 
  1 4 2 
  1 4 3 
  1 4 4 
  2 1 1 
  2 1 2 
  2 1 3 
  2 1 4 
  2 2 1 
  2 2 2 
  2 2 3 
  2 2 4 
  2 3 1 
  2 3 2 
  2 3 3 
  2 3 4 
  2 4 1 
  2 4 2 
  2 4 3 
  2 4 4 
  3 1 1 
  3 1 2 
  3 1 3 
  3 1 4 
  3 2 1 
  3 2 2 
  3 2 3 
  3 2 4 
  3 3 1 
  3 3 2 
  3 3 3 
  3 3 4 
  3 4 1 
  3 4 2 
  3 4 3 
  3 4 4 
  4 1 1 
  4 1 2 
  4 1 3 
  4 1 4 
  4 2 1 
  4 2 2 
  4 2 3 
  4 2 4 
  4 3 1 
  4 3 2 
  4 3 3 
  4 3 4 
  4 4 1 
  4 4 2 
  4 4 3 
  

전체 소스 코드

#include "header.h"
using namespace std;
int visit[5];
void print(vector<int>&candidates) {
  for(auto a : candidates) cout << a << ' ';
  cout << endl;
}

void init(vector <int> &ans) {
  ans.clear();
  memset(visit, 0, sizeof(visit));
}

void combination(vector<int>&candidates, vector <int>&num, int idx, int cnt) {
  if(candidates.size() == cnt) {
    print(candidates);
    return;
  }

  for(int i=idx; i<num.size(); i++) {
    if(!visit[i]) {
      visit[i] = 1;
      candidates.push_back(num[i]);
      combination(candidates, num, i+1, cnt);
      candidates.pop_back();
      visit[i] = 0;
    }
  }
}

void permutation(vector<int>&candidates, vector <int>&num, int cnt) { // 조합
  if(candidates.size() == cnt) {
    print(candidates);
    return;
  }

  for(int i=0; i<num.size(); i++) {
    if(!visit[i]) {
      visit[i] = 1;
      candidates.push_back(num[i]);
      permutation(candidates, num, cnt);
      candidates.pop_back();
      visit[i] = 0;
    }
  }
}

void duplicate_combination(vector<int>&candidates, vector <int>&num, int idx, int cnt) {
  
  if(candidates.size() == cnt) {
    print(candidates);
    return;
  }

  for(int i=idx; i<num.size(); i++) {
    candidates.push_back(num[i]);
    duplicate_combination(candidates, num, i, cnt);
    candidates.pop_back();
  }
}

void duplicate_permutation(vector<int>&candidates, vector <int>&num, int cnt) {
  
  if(candidates.size() == cnt) {
    print(candidates);
    return;
  }

  for(int i=0; i<num.size(); i++) {
    candidates.push_back(num[i]);
    duplicate_permutation(candidates, num, cnt);
    candidates.pop_back();
  }
}
int main() {
  vector <int> num = {1, 2, 3, 4};
  vector <int> ans;

  cout << "조합 구현" << endl; // 중복 X, 순서 X
  combination(ans, num, 0, 3); // 답을 저장할 벡터, 숫자들, 인덱스, 얼마나 뽑을 것인지
  init(ans);
  
  cout << "\n순열 구현" << endl; // 중복 X, 순서 O≠
  permutation(ans, num, 3); // 답을 저장할 벡터, 숫자들, 얼마나 뽑을 것인지
  init(ans);

  cout << "\n중복 조합" << endl; // 중복 O, 순서 X
  duplicate_combination(ans, num, 0, 3); // 답을 저장할 벡터, 숫자들, 얼마나 뽑을 것인지
  init(ans);

  cout << "\n중복 순열" << endl; // 중복 O, 순서 O
  duplicate_permutation(ans, num, 3); // 답을 저장할 벡터, 숫자들, 얼마나 뽑을 것인지

  return 0;
}

관련 문제

조합

Combination Sum

Letter Combinations of a Phone Number

순열

Letter Case Permutation

Permutations