[BOJ] 백준 15652 N과 M(4)

출처: https://www.acmicpc.net/problem/15652

 Input 
4 2

 Output 

1 1

1 2

1 3

1 4

2 2

2 3

2 4

3 3

3 4

4 4

중복을 허용하는 조합 문제이다.

중복 없는 조합과 문제 [BOJ] 15650 N과 M (2)와 달리 기존의 선택한 원소를 다시 선택할 수 있다.

 

▶ 순열과 조합 (백준 N과 M 시리즈) 

순열과 조합 (백준 N과 M 시리즈)

---

C / C++

#include <stdio.h>

const int MAX_N = 8 + 2;
int N, M, ans[MAX_N];
bool visited[MAX_N];

void DFS(int idx, int depth) {
    if (depth == M) {
        for (int i = 0; i < M; ++i) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    for (int i = idx; i < N; ++i) {
        ans[depth] = i + 1;
        DFS(i, depth + 1);
        ans[depth] = 0;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &M);
    DFS(0, 0);
}

 

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
      
     static int[] arr, output;
    static int N, M;
     
    public static void main(String[] args) {
        Scanner sc = new  Scanner(System.in);
         
        N = Integer.parseInt(sc.next());
        M = Integer.parseInt(sc.next());
         
        arr = new int[N];
        for(int i=0; i < N; i++) {
            arr[i] = i+1;
        }
        // 뽑힌 원소를 알아내기 위한 배열
        List<Integer> output = new ArrayList<>();
         
        // 원소를 뽑기 시작할 배열상의 위치와
        // 조합으로 뽑힌 원소들을 저장할 리스트를 인자로  전달.
        combination(0, output);
    }
     private static void combination(int idx,  List<Integer> output) {
           
          // 이미 원하는 길이의 조합을 만족했으면 출력하고  종료  
          if(output.size() >= M) {
            // 지금까지 방문한(뽑힌) 원소를 출력한다.
            for(int i=0; i<M; i++) {
              System.out.print(output.get(i) + " ");
            }
            System.out.println();
              return;
          }
           
          // 더 이상 뽑을 원소가 없다면 길이를 만족하지  못하는 조합을 하고 있었던 것이다.
          if(idx >= N) {
              return;
          }
           
          // 중복없는 조합은 의미가 간단하다.
          // 이번 index의 원소를 뽑거나 안 뽑거나이다.
          // 이번 원소를 뽑고 전달한다.
          output.add(arr[idx]);
         
          // 중복 조합의 경우 현재 idx의 원소를 뽑고  다음번에도 다시 뽑을 수 있게 해주면된다.
          // 다음번에 중복해서 뽑을 수 있고 안 뽑고 재귀로 다음 인덱스로 넘어갈 수 있다.
                    // 중복 없는 조합과 유일한 차이점
          combination(idx, output);
           
          // 뽑지 않은 경우는 위에서 넣었던 원소를 다시 빼서  전달한다.
          output.remove(output.size()-1);
          combination(idx+1, output);
     }
}