[재귀] 조합

두 정수 n,k를 입력받아 k개의 1을 가진 n자리 이진 패턴을 출력

package com.company;

public class Main {

    static int N, K;

    public static void main(String[] args) {

        N=4;
        K=2;

        int[] arr = new int[K];
        combination(arr, 0, N, K,0);
    }


    public static void combination(int[] arr, int index, int n, int r, int target) {
        if(r==0) print(arr, index);
        else if (target==n) return;
        else {
            arr[index] = target;
            combination(arr, index+1, n, r-1, target+1);
            combination(arr, index, n, r, target+1);
        }
    }

    public static void print(int[] arr, int length) {

        for(int i=0; i<length; i++){
            System.out.print(arr[i]);
        }
        System.out.println();


        int[] binary = new int[N];

        for (int i=0; i<length; i++){
            binary[ arr[i] ] = 1;
        }

        //출력
        for(int i = 0; i< N; i++){
            System.out.print( binary[i] );
        }
        System.out.println("");
    }
}

01

1100

02

1010

03

1001

12

0110

13

0101

23

0011

public static void combination(int[] arr, int index, int n, int r, int target) {
        if(r==0) print(arr, index);
        else if (target==n) return;
        else {
            arr[index] = target;
            combination(arr, index+1, n, r-1, target+1);
            combination(arr, index, n, r, target+1);
        }
    }

2019. 10. 10

/q는 r의 초깃값 백업
static void nCr(int n, int r, int q){

    if(r==0){
        printArr(q);
    }else if(n<r){
        //말이안됨
        return;
    }else{
        t[r-1] = arr[n-1];
        nCr(n-1, r-1, q);
        nCr(n-1, r, q);
    }
}