순열 조합 알고리즘을... 또 까먹은 듯 하여 코테를 앞두고 정리하고자 한다.
그만 까먹어...🥹

순열

전체 배열에서 순서에 상관있게 r개를 뽑는 경우.
중복으로 뽑으면 안되므로, 해당 숫자를 사용했음을 나타내는 visited[] 배열이 필요하다.

매개변수

• int[] arr : 전체 배열
• int[] res: 결과 배열 (R개를 뽑아라! 했으면 R개가 담긴 배열)
• boolean[] visited : 중복되면 안되므로 방문 체크하는 배열
• int depth: 현재까지 뽑은 개수
• int r : 뽑을 개수

코드

void permutation(int[] arr, int[] res, boolean[] visited, int depth, int r){
	if(depth==r){
    	//다 뽑은 경우 수행할 함수 실행
        //예시 : 뽑은 애들 나열
        for(int i=0;i<res.length;i++){
        	System.out.print(res[i]+" ");
            return;
        }
    }
    for(int i=0;i<arr.length;i++){
    	if(!visited[i]){
        	visited[i] = true;
            res[depth] = arr[i];
            permutation(arr,res,visited,depth+1,r);
            visited[i] = false;
        }
    }
}

중복순열

순열에서 중복을 허용한 코드.
visited 배열이 필요 없어진다.

코드

void rePermutation(int[] arr, int[] res, int depth, int r){
	if(depth==r){
    	//다 뽑고 수행할 함수 
        return;
    }
    for(int i=0;i<arr.length;i++){
    	res[depth] = arr[i];
        permutation(arr,res,depth+1,r);
    }
}

조합

N개에서 R개를 뽑는데 순서는 상관없게 뽑는 경우. 순열 코드에 idx 파라미터를 추가하여, 자신보다 큰 수만 뽑을 수 있게 수정해준다.
visited[] 배열은 필요없다.

매개변수

• int[] arr : 전체 배열
• int[] res : 결과 배열
• int depth : 현재 뽑은 개수
• int r : 뽑아야 하는 개수
• int idx : 현재 위치

코드

void combination(int[] arr, int[] res,int depth, int r, int idx){
	if(depth==r){
    	//다 뽑고 실행할 함수
        return;
    }
    for(int i=idx;i<arr.length;i++){
    	res[depth] = arr[i];
      	combination(arr,res,visited,depth+1,r,i+1);

    }
}

중복조합

조합에서 중복을 허용한 경우.
다음 반복문을 시작하는 값을 조합에서는 +1 하면서 재귀 돌렸지만 여기서는 +1 하지 않는다. 중복이 허용되기 때문

void repCombination(int[] arr, int[] res, int depth, int r, int idx){
	if(depth==r){
    	return;
    }
    
    for(int i=idx;i<arr.length;i++){
    	res[depth] = arr[i];
        repCombination(arr,res,depth+1,r,i);
    }
}