본문 바로가기
Java

백트래킹을 이용한 순열 in java

by onejunu 2020. 8. 30.
static ArrayList<List<Integer>> nPkV2(int[] arr,int k){
        ArrayList<List<Integer>> ret = new ArrayList<>();
        boolean[] visited = new boolean[arr.length];
        int[] resList = new int[k];
        nPkdfsV2(ret,arr,resList,visited,k,0);
        return ret;
    }

static void nPkdfsV2(ArrayList<List<Integer>> ret,
    int[] arr,
    int[] resList,
    boolean[] visited,
    int k,int idx){
            if(k==idx){
                  List<Integer> tmp = new ArrayList<>();
                  for(int i=0;i<k;i++){
                         tmp.add(resList[i]);
                  }
                  ret.add(tmp);
            }else{
                  for(int i=0;i<arr.length;i++){
                      if(visited[i]) continue;

                      visited[i]=true;
                      resList[idx]=arr[i];
                      nPkdfsV2(ret,arr,resList,visited,k,idx+1);
                      visited[i]=false;
                  }
            }
 }

댓글