로또 6603

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

이문제는 조합이다 순열이 아니다.

순열은 순서가 있는 조합
순열은 같은 원소라도 순서가 다르면 다른것이다.

조합은 순서가 없다. 같은 원소면 같은 것이라 중복처리해야함. 개념설명이 오히려 헷갈리게 한다. AB와 BA는 같은것이라고 하는게 조합이다. 근데 순서가 없다는게 이해가 안된다. 순서가 중요하지 않으니 같은것이라고 봐야하나
난 오히려 순서가 중요하지 않으니 다른것이라고 이해되었는데.
조합은 순서가 중요하지 않으니 같은것이라고 봐야하나 보다.
조합은 O(2^N)
순열은 O(!N) 이다

K가 최대 12
O(2^N)

코드는 2510

import java.io.*;

public class Main
{
    static BufferedReader br;
    static int K;
    static int[] S;

    static boolean[] check;
    static final int LOTTO_LEN = 6;
    static int[] arr = new int[LOTTO_LEN];


    static StringBuilder sb = new StringBuilder();

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

        String[] input;

        while(true)
        {
            input = br.readLine().split(" ");
            if(Integer.parseInt(input[0]) == 0)
                break;

            K = Integer.parseInt(input[0]);
            S = new int[K];
            check = new boolean[K];

            for(int i = 0; i < K; ++i)
            {
                S[i] = Integer.parseInt(input[i+1]);
            }

            search(0, 0);
            sb.append("\n");
        }

        System.out.println(sb);
    }

    public static void search(int depth, int start)
    {
        if(depth == LOTTO_LEN)
        {
            for(int i = 0; i < LOTTO_LEN; ++i)
            {
                if(i != LOTTO_LEN-1)
                    sb.append(arr[i] + " ");
                else
                    sb.append(arr[i] + "\n");
            }
            return;
        }

        for(int i = start; i < K; ++i)
        {
            if(false == check[i])
            {
                check[i] = true;
                arr[depth] = S[i];
                search(depth+1, i);
                check[i] = false;
            }

        }
    }
}