다른 점은
중복
!
-> 순열에서는visited
배열을 사용해서, 해당 항목이 중복이 아닌지를 체크해야 한다.
계속 사용되는 배열, arraylist는 재귀 함수 내부에서 생성하지 않고, 외부에서 생성해서 인자로 전달해줌
(재귀 내에서 생성하면, 계속 새롭게 생성되기 때문에)
public class Solution {
public static ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
ArrayList<Integer> freshArr = new ArrayList<>();
ArrayList<Integer[]> result = new ArrayList<>(); // 전체 결과값
// 0이 3개 이상인 재료는 상한 재료 -> 제외
for(int stuff: stuffArr){
String value = String.valueOf(stuff);
if(value.chars().filter(e-> e=='0').count() < 3){
freshArr.add(stuff);
}
}
// 재료가 비거나, choicNum보다 작을 때
if(freshArr.isEmpty() || freshArr.size() < choiceNum) return null;
// 정렬
Collections.sort(freshArr);
boolean[] visited = new boolean[freshArr.size()];
return permutation(freshArr, choiceNum, visited, new Integer[]{}, result);
}
public static ArrayList<Integer[]> permutation(ArrayList<Integer> freshArr, int choiceNum, boolean[] visited, Integer[] array, ArrayList<Integer[]> result) {
if(choiceNum==0){ // 탈출 조건
result.add(array);
return result;
}
for(int i=0;i<freshArr.size();i++){
if(!visited[i]) { // 방문한 적이 없다면(중복 체크)
visited[i]=true;
Integer[] newArr = Arrays.copyOf(array, array.length + 1);
newArr[newArr.length - 1] = freshArr.get(i);
result = permutation(freshArr, choiceNum - 1, visited, newArr, result);
visited[i] = false; // 한번 재귀를 순회한 이후, 반복문을 다시 시작하기 위해 첫 시작 원소를 false로 설정
}
}
return result;
}
}
dept
를 추가public class Solution {
public static ArrayList<Integer[]> newChickenRecipe(int[] stuffArr, int choiceNum) {
ArrayList<Integer> freshArr = new ArrayList<>();
ArrayList<Integer[]> result = new ArrayList<>(); // 전체 결과값
// 0이 3개 이상인 재료는 상한 재료 -> 제외
for(int stuff: stuffArr){
String value = String.valueOf(stuff);
if(value.chars().filter(e-> e=='0').count()<3){
freshArr.add(stuff);
}
}
// 재료가 비거나, choicNum보다 작을 때 return null
if(freshArr.isEmpty() || freshArr.size() < choiceNum) return null;
// 정렬
Collections.sort(freshArr);
boolean[] visited = new boolean[freshArr.size()];
return permutation(freshArr, 0, choiceNum, visited, new Integer[freshArr.size()], result);
}
public static ArrayList<Integer[]> permutation(ArrayList<Integer> freshArr, int dept, int choiceNum, boolean[] visited, Integer[] array, ArrayList<Integer[]> result) {
if(dept == choiceNum){ // 탈출 조건
result.add(array);
return result;
}
for(int i=0;i<freshArr.size();i++){
if(!visited[i]) { // 방문한 적이 없다면
visited[i]=true;
Integer[] newArr = Arrays.copyOf(array, array.length);
newArr[dept] = freshArr.get(i);
result = permutation(freshArr, dept+1, choiceNum, visited, newArr, result);
visited[i] = false;
}
}
return result;
}
}