[백준] 15652번: N과 M (4)

문제 내용

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

15652번: N과 M (4)

 

풀이 시간

4분

풀이 과정

백트래킹을 이용해 풀이

중복조합을 구현하는 간단한 풀이

 

정답 코드

 

1. 파이썬

import sys
sys_input=sys.stdin.readline

n,m=map(int,sys_input().rstrip().split())

ans=[]

def back_tracking(prev):
    if len(ans)==m:
        for x in ans:
            print(x,end=" ")
        print()
        return

    for i in range(prev,n+1):
        ans.append(i)
        back_tracking(i)
        ans.pop()

back_tracking(1)

 

 

2. 자바

import java.io.*;
import java.util.*;

public class Main {
    public static int n, m;
    public static List<Integer> cur = new ArrayList<>();

    public static void back_tracking(int prev) {
        if (cur.size() == m) {
            for (int x : cur) {
                System.out.print(x + " ");
            }
            System.out.println();
            return;
        }

        for (int i = prev; i <= n; i++) {
            cur.add(i);
            back_tracking(i);
            cur.remove(cur.size() - 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        back_tracking(1);
    }
}