순열,중복순열,조합,중복조합 정리

순열 (Permutation) -> 시간복잡도 O(n!)

서로 다른 N개에서 R개를 뽑아 정렬하는 경우의 수

서로다른 N개에서 R개를 뽑는것은 순열,중복순열,조합,중복조합 모두 같다.

하지만 순열은 "정렬"하는 경우의 수를 생각한다는것이 다른점이다.

두가지원소 1,2를 뽑아 [1,2]로 정렬하는 경우와1,2를 똑같이 뽑고 [2,1]로 정렬하는 경우가 서로다르다고 카운팅하는것이 순열이다.

이런 순열을 자바에서는 어떻게 구현할까

일단 순열은 기본적으로 재귀적인 방식으로 구현하는 완전탐색 방식이며

 

순열을 이용할때 주의사항

* 순열은 조합과 다르게 반복문 시작인덱스를 매개변수로 보내지않아도되고, 0으로 반복문을 시작하면 된다 (반복문 시작 인덱스가 0 이라는것은 ,순서가 다르게도 뽑겠다는뜻)
* 조합과 다르게 visited 방문배열로 뽑은값을 출력하면 안된다 -> 1과 2가 visited에서 true라고 했어도 이게 (1,2)도 이렇게 나타나고 (2,1)도 이렇게 표현되므로
* 즉 visited 배열 반복문 순회로 뽑힌것을 출력하면 (1,2)와 (2,1)이 구분이 안되기 때문이다.

2가지 방법을 이용해구현할 수 있다.

1.  DFS 방식 [   visited 방문배열 이용 (사전순으로 출력)] 

public class Main {

    public static void main(String[] args) {
        int[] arr = {1,2,3};  // 뽑아야 하는 요소들을 저장한 배열
        int n = 3; //전체갯수를 의미하는 n은 arr.length로 표현가능하므로 스킵가능.
        int r = 3; // 뽑아야하는 갯수
        int[] result = new int[3]; //결과를 저장할 배열
        int depth =0;  //depth는 트리형태로 보면 깊이로 볼 수 있고 , 간단히 생각하면 (뽑은 갯수 -1) 로 볼 수 있다. {0부터 시작하므로}
        boolean[] visited = new boolean[n]; //방문배열
        permutation(arr,result,visited,r,depth);


    }

    static void permutation(int[] arr,int[] result ,boolean[] visited ,int r,int depth) // 전체갯수인 n을 안줘도 arr.length로 대체가능해서 스킵.
    {
        if(depth == r) //재귀적으로 함수가 실행되다가 뽑은 최대갯수를 넘었을때
        {
            System.out.println(Arrays.toString(result)); // 하나하나뽑아 result에 저장한 결과를 출력한다.
            return; //해당 함수 종료
        }

        for(int i=0;i<arr.length;i++) // 뽑아야하는 전체를 돌림.
        {
            if(!visited[i]) //방문하지않았다면 (뽑지않았다면)
            {
                visited[i] = true; //방문체크 ( 뽑아준다)
                result[depth] = arr[i]; // depth는 현재 뽑은 갯수-1 를 의미하므로 depth를 이용하여 뽑은걸 알맞은 위치에 저장
                permutation(arr,result,visited,r,depth+1); //depth를 증가시켜 permutation 메소드 실행
                visited[i] = false; // 방문했던걸,뽑았던걸 false로 해준다 -> 다른경우로 넘어가기위해
            }

        }

    }

}

결과

visited 방문배열을 이용하여 하나 뽑고 순열메소드를 다시 실행하여 다음으로 넘어가고를 반복하다 r개를 다 뽑았을때
재귀적으로 실행된 메소드들이 하나씩 종료되면서 방문배열도 다시 방문을 취소해주는 방식이다.

그래프에서 dfs 동작방식

DFS(깊이 우선탐색)을 하면서 첫번째 요소부터 만들 수 있는 경우를 다 만들고 넘어가기 때문에
결과값이 사전순으로 나온다는 장점이 있다. ( swap을 이용하는 경우 출력값이 사전순으로 나오지않음)

방문배열을 이용한 순열의 동작방식

visited 방문배열과 result(결과를 담는)배열을 이용하여 하나씩 채워가는 느낌.

ex) 뽑을것들 1,2,3,4,5 가 있을때
첫번째 요소를 뽑고 ,순열 메소드가 실행되고를 반복하여
visitied[true,true,true,false,false] 로 [1,2,3]을 뽑고 난후 3을 뽑은 순열 메소드가 종료되면
2를뽑은 메소드로 돌아와서 그 다음 명령문인

visited[i] = false;

를 실행하게 되고
그러면 현재 visitied 배열은 visitied[true,true,false,false,false] 가 될것이다. 그 후 겉에있는 반복문으로 인해 i는 3이 될것이고 방문을 true로 바꾸면 visitied[true,true,false,true,false] 가 될것이다. 그렇다면 뽑은것은 [1,2,4]가 된다.
이런식의 반복.

 

---

 DFS 를 이용한 순열  예시 [Visited를 이용한] 

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    /**
     * 예제를 보면 순열의 에제와 같다는것을 알 수 있다.
     * 순열은 조합과 다르게 반복문 시작인덱스를 매개변수로 보내지않아도되고, 0으로 반복문을 시작하면 된다 (반복문 시작 인덱스가 0 이라는것은 ,순서가 다르게도 뽑겠다는뜻)
     * 조합과 다르게 visited 방문배열로 뽑은값을 출력하면 안된다 -> 1과 2가 visited에서 true라고 했어도 이게 (1,2)도 이렇게 나타나고 (2,1)도 이렇게 표현되므로
     * 즉 visited 배열 반복문 순회로 뽑힌것을 출력하면 (1,2)와 (2,1)이 구분이 안되기 때문이다.
     *
     * 순열이 동작할때 필요한 매개변수들 -> int n, int r, 뽑을 리스트, 중복방지 방문배열, 뽑은결과 저장할배열, 결과저장할때 인덱스로 쓰고 다 뽑았는지 체크하기위한 depth변수
     * 즉 int n, int r, int[] arr ,boolean[] visited,int[] result , int depth 정도이다.
     * 여기서 int n , int r, int[] arr, boolean[] visited 정도는 static 전역변수로 빼놔도 된다.
     */
    static boolean[] visited;
    static int[] result;
    static int n;
    static int r;

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        r = Integer.parseInt(input[1]);
        visited = new boolean[n];
        result = new int[r];

        permutation(result,0);

        bw.flush();
        bw.close();

    }

    public static void permutation(int[] result,int depth) throws IOException{
        if (depth == r) {
            for (int i = 0; i < r; i++) { //뽑은것들 출력
                bw.write(result[i]+" ");
            }
            bw.newLine();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true; //방문배열 뽑았다고 체크
                result[depth]= i+1; //결과 저장에 해당 값 저장
                permutation(result,depth+1); //depth 증가시키며 재귀실행
                visited[i] = false; // 방문배열 안뽑았다고 수정 , result는 알아서 값이 덮어쓰여진다.
            }
        }

    }


}

위의 예시 문제

백준/15649 N과 M(1) // 순열

 

 

 

 

2. swap을 이용 (순서가 보장되지않는다.) -> 참고용

swap은 depth를 기준으로 하나씩 값을 고정시켜가면서 진행한다고 보면된다. (depth인덱스 위치값을 어떤 인덱스위치값이랑 바꿀지 바꿔가며 모든 경우의 수를 구하는)
swap(자리바꾸기)는 자기자신과 자기자신을 바꾸는 제자리 스왑도 진행한다.

swap을 이용한 순열로 경우의수를 구하는법 -> 자리별로 하나씩 고정시킨다.
depth를 기준으로 depth보다 작은 인덱스는 고정시킨다고 보면된다.

public class Main {

    public static void main(String[] args) {
        int[] arr = {1,2,3};  // 뽑아야 하는 요소들을 저장한 배열
        int r = 3; // 뽑아야하는 갯수
        int depth =0;  //depth전 요소들은 고정된 요소들, depth부터 swap
        permutation(arr,r,depth);


    }

    static void permutation(int[] arr,int r,int depth)
    {
        if(depth == r)
        {
            System.out.println(Arrays.toString(arr));
            return;
        }

        for(int i = depth; i<arr.length;i++)
        {
            swap(arr,depth,i);
            permutation(arr,r,depth+1);
            swap(arr,depth,i);
        }


    }
    static void swap(int[] arr, int a,int b)
    {
        int temp= arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

}

 

결과

swap을 이용한 순열 동작방식

예) 위의 그림과 함께보는 123이 뽑히는 동작방식
depth가 0일때 아무것도 고정되어있지않음
swap(1,1)을 진행하여 -> swap(depth,반복문의 현재인덱스) {반복문의 인덱스는 depth부터 시작하므로 항상 depth보다큼}
첫번째 자리를 고정시킨다 (여기서는 제자리 스왑을 함)
depth를 증가시켜 전달하여 다음 순열메소드를 실행
depth가 1이므로 반복문 인덱스가 1부터 시작 ( 0번째 배열요소는 건들지않음 -> 이런식으로 고정값이됨)
이렇게
depth가 2까지 가고 모든배열요소가 고정되고 난후
다음 순열메소드로 넘어가면 depth가 3이므로 종료된다.
종료후 depth가 2이였던 메소드에서 다음 명령문인
swap이 실행되며 바꿔놨던것을 다시 원래대로 돌려놓는다
(방문배열을 이용한 순열에서
순열메소드가 종료시 다음 명령문이 방문했던것을 다시 false로 두는것처럼)

중복순열

서로다른 n개에서 "중복이 가능하게" r개 뽑아 "정렬"한 경우의 수

visited 방문배열을 이용한 순열에서 방문배열을 사용했던 이유는 중복을 막기 위해서인데
중복 순열은 중복해서 요소를 뽑을 수 있으므로 방문배열 부분을 삭제해서 중복을 허용한다.

public class Main {

    public static void main(String[] args) {
        int[] arr = {1,2,3};  // 뽑아야 하는 요소들을 저장한 배열
        int r = 3; // 뽑아야하는 갯수
        int depth =0;  //dfs로 동작하니까 깊이를 표시할 변수.
        int[] result = new int[arr.length];
        permutation(arr,result,depth,r);


    }

    static void permutation(int[] arr,int[] result , int depth,int r)
    {
        if(depth ==r)
        {
            System.out.println(Arrays.toString(result));
            return;
        }

        for(int i=0;i<arr.length;i++)
        {
            result[depth] = arr[i];
            permutation(arr,result,depth+1,r);
        }


    }


}

 

결과

 

중복 순열 코드, 예제

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    /**
     * 중복 순열
     * 중복을 막는 방문배열을 없앤다.
     */

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int r = Integer.parseInt(input[1]);
        int[] result = new int[r];
        permutation(n, r,  result, 0);
        bw.flush();
        bw.close();

    }

    public static void permutation(int n, int r,int[] result,int count) throws  IOException{
        if (count == r) {
            for (int i = 0; i < r; i++) {
                bw.write(result[i] + " ");
            }
            bw.newLine();
            return;
        }
        for (int i = 0; i < n; i++) {
            result[count] = i + 1; //결과값을 저장할때 인덱스는 지금까지 뽑은갯수여야만 한다.
            permutation(n, r,result,count+1);
        }

    }

}

https://keeeeeepgoing.tistory.com/101

백준/15651 N과 M (3) // 중복 순열

 

 

 

---

조합 - Combination  시간복잡도 O(2^n)   [ 조합 == 이항계수]

서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

(정렬이 같지않아도 뽑은개 같다면 같은 경우의 수로 본다) -> [1,2,3] 이나 [1,3,2] 나 같은걸로 봄.

[부분집합이라 생각하면된다.]

동작방식 -> 해당 인덱스를 뽑거나 안뽑거나를 반복한다.

 

조합은 visited[] == 방문배열 을 이용해서 뽑은걸 출력해도 된다 (순열은 안됨)

순열과 조합의 차이점.

* 순열은 조합과 다르게 반복문 시작인덱스를 매개변수로 보내지않아도되고, 0으로 반복문을 시작하면 된다 (반복문 시작 인덱스가 0 이라는것은 ,순서가 다르게도 뽑겠다는뜻)
* 조합과 다르게 visited 방문배열로 뽑은값을 출력하면 안된다 -> 1과 2가 visited에서 true라고 했어도 이게 (1,2)도 이렇게 나타나고 (2,1)도 이렇게 표현되므로
* 즉 visited 배열 반복문 순회로 뽑힌것을 출력하면 (1,2)와 (2,1)이 구분이 안되기 때문이다.

---

조합응용 - 파스칼 삼각형  

nCr -> n-1Cr-1 + n-1Cr

예) 5C2 -> 4C1 + 4C2 

5C0 ,5C5 -> 1 

파스칼의 삼각형과 이항계수의 성질

https://keeeeeepgoing.tistory.com/94  응용문제

조합의 시간복잡도는 O(2^N)이다.  n이 크거나 , 시간제한이 짧을때 조합을 그냥사용하면 시간초과에 걸린다. 그때 파스칼의 삼각형을 사용한다. 파스칼의 삼각형은 다이나믹 프로그래밍(메모이제이션)을 이용한다.

 

관련된 문제

https://keeeeeepgoing.tistory.com/97

백준/1010 다리놓기

---

 

0. 방문배열없이

조합에서는 반복문의 인덱스가 가장 중요하고 

반복문의 인덱스를 이용해서 순서만 다른게 안뽑히게 하고, 

똑같은것이 안뽑히게한다.

 

순열에서는 뽑을것들을 매번 처음부터 살펴보기때문에 다시 뽑히지않게 방문배열이 필요한거고

조합에서는 필요없는거같다.

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int n;
    static int target;
    static int result;
    static int[] cards;

    public static void main(String[] args) throws IOException {
        input();
        solve();

        bw.flush();
        bw.close();

    }

    static void input() throws IOException {

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        target = Integer.parseInt(input[1]);
        cards = new int[n];
        input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            cards[i] = Integer.parseInt(input[i]);
        }
    }

    static void solve() throws IOException {
        combi(n, target, 0, 0, 0);
        System.out.println(result);

    }

    static void combi(int n, int target, int index, int depth, int sum) {
        if (depth == 3) {
            if (sum <= target) {
                if (sum > result) {
                    result = sum;
                }
            }
            return;
        }

        for (int i = index; i < n; i++) {

            combi(n, target, i + 1, depth + 1, sum + cards[i]);


        }
    }


}

 

백준 블랙잭문제에 대한 답인데  방문배열을 사용한것보다 빠름,

조합이 동작하는것을 생각하면 방문배열이 필요없는거같다.

---

 

 

 

 

1. DFS + 백트래킹을 이용한 방법 

백트래킹 -> ( 해가없으면 건너띄어서 시간효율을 높인 방법, 동작방식은 dfs라 볼 수 있다.)
해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다.
최적화 문제와 결정 문제를 푸는 방법이 됩니다. -> dfs에서 해가될 가능성이 없는경우를 가지치기하면서 진행하는방법

백트래킹과 DFS의 차이점?

알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

public class Main {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};  // 뽑아야 하는 요소들을 저장한 배열

        int r = 2; // 뽑아야하는 갯수
        int start =0; // 반복문이 시작하는 인덱스  , 뽑을지말지 선택하는 시작 인덱스

        int[] result = new int[arr.length];
        boolean[] visited = new boolean[arr.length];

        combination(arr, visited, start, r);



    }

    static void combination(int[] arr,boolean[] visited,int start,int r)
    {
        if(r == 0) // 뽑아야하는 갯수가 0이면
        {
            for(int a=0;a<arr.length;a++)
            {
                if(visited[a]) //뽑은거라면
                {
                    System.out.print(String.format("%d ", arr[a])); //출력
                }
            }
            System.out.println(); //한줄띄기
        }
        for(int i=start;i<arr.length;i++)
        {
            visited[i] = true; // 해당 요소 선택
            combination(arr,visited,i+1,r-1); // 시작 인덱스는 반복문의 현재 인덱스 +1 하고 , 뽑아야할 갯수는 하나 줄이고
            visited[i] =false;

        }
    }


}

가장중요 => start로 전달하는값은 현재 반복문의 인덱스이다.  i+1 이다.

(start+1 하면안됨)

start는 반복문을 시작하는 인덱스를 의미하고
새로운 combination에 현재인덱스 +1 , 뽑아야할수 -1 를 건네준다.

2. 재귀를 이용한 방법

public static void combination( int count,int depth) {
    if (count == k) { //다 선택한경우
        result++;
        return;
    }
    if (depth == n) {
        return;
    }
    visited[depth] = true;
    combination(count + 1, depth + 1);
    visited[depth] = false;
    combination(count, depth + 1);

}

count 또는 r 변수로 몇개를 선택했는지 체크하고 , depth를 이용하여 지금 어디 위치에서 선택할지 말지 결정하는지를 체크할 수 있다. ( depth가 dfs방법에서의 start변수 느낌)

재귀를 이용하므로 depth변수를 다시 사용한다.

https://minhamina.tistory.com/m/38

[Java] 조합 Combination

[Combination]- Java코드 (DFS, BFS 방식 -성능비교)

조합에서 start+1가 아닌 i+1를 넘겨줘야하는것을 잊지말자

현재 반복문의 인덱스 그 다음걸 넘겨줘야한다. + depth가 뽑은갯수로 볼수있고 r이 타겟넘버로 볼수있다(뽑아야하는갯수)

재귀를 이용한 dfs 느낌

중복 조합

서로다른 n개에서 r개를 뽑을때 순서없이 중복가능하게 뽑는다.
중복이 되지않게 사용했던 방문배열 사용을 없앤다.
방문배열을 이용하여 결과값을 뽑았는데 없앴으니
결과를 저장할 배열을 추가해줌.

 

정리 :

선택하고 안하고에 쓰이는 방문배열 없애고 ,

조합 재귀호출때 반복문 인덱스 +1 하지않고 그냥 현재 인덱스를 전달해준다 ( 중복 선택 되게끔)   

, depth를 count로 바꿔도됨 == 결국 몇개 선택했냐를 체크하는 변수

public class Main {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};  // 뽑아야 하는 요소들을 저장한 배열

        int r = 2; // 뽑아야하는 갯수
        int start =0; // 반복문이 시작하는 인덱스  , 뽑을지말지 선택하는 시작 인덱스

        int[] result = new int[r];

//        boolean[] visited = new boolean[arr.length];

        int depth =0;

        combination(arr, result, start, r, depth);



    }

    static void combination(int[] arr,int[] result,int start,int r,int depth)
    {
        if(depth == r)
        {
            System.out.println(Arrays.toString(result));
            return;
        }

        for(int i=start;i<arr.length;i++)
        {
            result[depth] = arr[i];
            combination(arr, result, i, r, depth+1);
        }


    }


}

결과

중복조합 구현해보기

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    /**
     * 조합을 이용하는 문제인데 ,같은수를 여러번 골라도 되는 중복 조합 문제이다.
     * 중복을 막는 visited 방문배열없어야하고 ,거기다가 배열 시작인덱스 start값을 전달할때 증가해서 전달하면 안된다. 뽑았던걸 한번 더 뽑을수 있게끔.
     * 그리고 결과 출력용 배열이 필요하다.
     * static으로 전역변수화 해버리면 중복조합의 매개변수 갯수는 줄어든다.
     * 하지만 전역변수로 빼지않고 메소드화 하면 ,int n, int r,int start ,결과저장배열 ,뽑은갯수 저장변수 의 매개변수들이 필요하다.
     */

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int r = Integer.parseInt(input[1]);
        int[] result = new int[r];
        combination(n, r, 0, result, 0);
        bw.flush();
        bw.close();

    }

    public static void combination(int n, int r, int start,int[] result,int count) throws  IOException{
        if (count == r) {
            for (int i = 0; i < r; i++) {
                bw.write(result[i] + " ");
            }
            bw.newLine();
            return;
        }
        for (int i = start; i < n; i++) {
            result[count] = i + 1; //결과값을 저장할때 인덱스는 지금까지 뽑은갯수여야만 한다.
            combination(n, r, i ,result,count+1);
        }

    }




}

중복 조합 예제

---

순열 -> 순서만 다르다면 안의 요소는 중복이 되도 되므로 반복문의 시작인덱스가 0이된다. (일반적인 dfs)

중복을 허용한다면 방문배열을 없앨것.

 

 

재료를 도는 반복문의 인덱스가 0부터 시작하는 이유 ,방문배열 배열을 사용하는 이유

순열의 인덱스가 0으로 시작하는 이유는 

이미 뽑힌 애들을 제외하고(중복을 없애기위해 ,visited(방문배열)을 보고 체크해서)

나머지 애들중 하나를 넣어서 새로운 순서까지만들기위해서다

 

위에 동작방식을 보면 비어있는 배열에서 시작하고

 

첫번째 숫자를 고를떄 각각 1,2,3 으로 시작하는 경우를 만들기위해 반복문 인덱스는 0으로 시작

1을 뽑고 visited[0] = true  한후(1을 뽑았다는 의미)   dfs() 하고 visited[0] = false (1을 뽑지않았다는 의미)를 하면 해당 반복문의 인덱스가 증가해서 1가되고 그다음 visited[1]이 true인지 검사후 , 

 visited[1] = true  한후(2을 뽑았다는 의미)   dfs() 하면

2로 시작되는 경우의 수를 만드는 dfs가 시작된것이다.

dfs했으니 다시 visited[1] = false하고  반복문 인덱스 증가해서 또 진행해보면

3으로 시작되는 경우의수를 만드는 dfs가 시작되고 반복문 인덱스가 끝까지 왔으니 종료된다.

이런식으로 모든 순열의 경우를 만듬.

 

즉 방문배열은 해당 재료를 골랐는지 안골랐는지 체크하는것이고

해당 재료를 고를떄마다 (true할때마다) 다른 변수(뽑힌 결과를 저장할 변수) 에 담는다면 결과를 확인할 수 있다.

 

---

조합 -> 순서보다는 안의 요소가 중복되면안되니까 모든 조합을 체크하면서 가야한다 ,인덱스는 지금까지 뽑은갯수 -> 이미 뽑았던거에서 조합을 고려하면 안되니까

1~5숫자중 3개를 뽑는 조합 결과

조합의 결과를 보면  첫번째요소는 1~5, 두번째요소는 2~5, 세번째 요소는 3~5만 나온다.

그 이유는 반복문의 시작인덱스가 뽑은갯수이기 때문이며, 

 

만약 1,2만 뽑힌상황에서 세번째 뽑힐 요소는 3,4,5 뿐이다. 

그 이유는 1,2는 뽑혔고 , 남은게 3,4,5이기 때문

 

만약 1,3이 뽑힌 상황에서 세번째 뽑힐 요소는 4,5 뿐이다. 

그 이유는 2를 1,3,2는 1,2,3과 같기때문이다.

 

위와같은 조합 경우를 만들기 위해 

반복문의 시작인덱스를 뽑은갯수로하면

 

1,2가 뽑힌상황에서 보면 시작인덱스는 3일테니 3,4,5 와 조합하여 만들어질것이며

 

1,3이 뽑힌상황을 보면 시작인덱스는 3이지만 방문배열(visited)때문에 4,5의 조합으로 만들어질것이다.

중복을 허용한다면 방문배열을 없애면된다. (중복조합)

 

 

뽑을 재료들을 반복문으로 돈다. 반복문으로 돌면서 재료 하나씩 넣어보는것
visited[i] = true로 하는 이유 -> 반복문은 뽑을 재료들과 관련있으니 인덱스도 뽑을 재료와 관련있다. , 이미 이 재료는 뽑았다라는것을 의미하기 위해, 재귀적으로 넘어간 다음 함수에서 같은걸 또 뽑는걸 방지하기위해

 

조합예시)

1234 중 3개를 뽑는경우

visited가 false가 되면서 해당 숫자를 뽑지않고 넘어가게 된다.

count가 3이 되면 return을 하면서 재귀적으로 실행된 함수들이 종료되는데 그때 그 함수가 실행됬던 함수로 돌아가므로 그 위치의 count값으로 돌아간다 즉 count가 3이여서 종료됬으면 자신을 호출했던 count가 2인 함수속으로 돌아간다.

3개중 2개를 뽑는다고 치면 바로 위그림 왼쪽 빨간 동그라미 부분과 같다.

3개중 2개가 뽑히는 과정

 

 

 

4개중 2개를 뽑는과정

for(int i=start;i<4;i++){
    if(!visited[i])
    {
        visited[i] = true;
        dfs(visited, count++,i+1);
        visited[i] = false;

    }
}

조합의 중요한점 -> 반복문 시작인덱스인 start를 매개변수로 사용해야한다는것

마지막에 현재인덱스의 +1을 넘겨줘야한다

 

그래야 만약 첫번쨰 뽑힌 숫자가 3일떄 3,4  를 뽑아낼수있음

 

그때 start를 i+1로 넘겨받고  start가 3이되면서 4만을 짚고 넘어가기때문

 

조합 : 현재 인덱스의 +1을 해서 넘겨준다

 

 

---

조합,순열은 재귀를 이용한 dfs느낌

 

내가 참고할 코드 (조합,순열 메소드의 매개변수를 이해하여 사용할것)

https://keeeeeepgoing.tistory.com/22?category=1009143
풀었던 조합 기초문제

https://keeeeeepgoing.tistory.com/23

풀었던 순열기초문제

---

참고,출처,더 자세히보기

[알고리즘] 순열, 중복순열, 조합, 중복조합 총정리 !

 

[알고리즘] 순열, 중복순열, 조합, 중복조합 총정리 !

 

조합 Combination (Java)