순열, 조합을 dfs 백트래킹으로 구현
def permutation(items, selected, visit, count):
if len(selected) == count:
print(selected)
return
for i in range(len(items)):
# 고르는 경우
if visit[i]:
continue
selected.append(items[i])
visit[i] = True
permutation(items, selected, visit, count)
selected.pop()
visit[i] = False
def combination(items, selected, visit, count, index):
# print(selected, visit, index)
if len(selected) == count:
print(selected)
return
for i in range(index, len(items)):
# 고르는 경우
if visit[i]:
continue
selected.append(items[i])
visit[i] = True
combination(items, selected, visit, count, i+1)
selected.pop()
visit[i] = False
items = [1, 2, 3, 4]
visit = [False for _ in range(len(items))]
# permutation(items, [], visit, 3)
combination(items, [], visit, 3, 0)
public class Solution {
private int n,r;
boolean[] visit;
private int[] items, selected;
public void printAllPermutation(int[] items, int count){
this.items = items;
this.n = items.length;
this.r = count;
this.selected = new int[r];
this.visit = new boolean[n];
permutation(0);
}
public void printAllCombination(int[] items, int count){
this.items = items;
this.n = items.length;
this.r = count;
this.selected = new int[r];
this.visit = new boolean[n];
combination(0,0);
}
private void permutation(int depth) {
if (depth == r) {
System.out.println(Arrays.toString(selected));
return;
}
for (int i = 0; i < n; i++) {
if (!visit[i]) {
visit[i] = true;
selected[depth] = items[i];
permutation(depth + 1);
visit[i] = false;
}
}
}
private void combination(int depth,int start) {
if (depth == r) {
System.out.println(Arrays.toString(selected));
return;
}
for(int i=start;i<n;i++){
if(!visit[i]){
visit[i] = true;
selected[depth] = items[i];
combination(depth+1,i+1);
visit[i] = false;
}
}
}
@Test
void test() {
int[] arr = new int[]{0,1,2,3,4};
printAllPermutation(arr,3);
System.out.println("-------------");
printAllCombination(arr,3);
}
}