조합, 순열(Combination, Permutation) - Java

chaemin·2024년 3월 21일

구현 기초

기초

목록 보기

21/21

해당 포스팅은 아래 링크와 제 풀이를 바탕으로 작성하였습니다.

✨순열(Permutation)

[1, 2] != [2, 1] (다른 것)

[1, 2]와 [2, 1]을 다른것으로 처리한다.

	public static void dfs(int depth, int start, int arr[]) {
		if(depth == 2) {
			list.add(arr.clone());
			return;
		}
		
		for(int i = 0; i < N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[depth] = i;
				dfs(depth+1, i+1, arr);
				visit[i] = false;
			}
		}
	}

▶실행결과

✨조합(Combination)

[1, 2] = [2, 1] (같은 것)

	public static void dfs(int depth, int start, int arr[]) {
		if(depth == 2) {
			list.add(arr.clone());
			return;
		}
		
		for(int i = start; i < N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				//arr[depth] = i;
				arr[depth] = i;
				dfs(depth+1, i+1, arr);
				visit[i] = false;
			}
		}
	}