java로 순열 구현

import java.util.ArrayList;

public class P {
	
	public static ArrayList<ArrayList<Integer>> p(int[] nums) {
		ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> curr = new ArrayList<Integer>();
		boolean[] used = new boolean[nums.length];
		
		backtrack(curr, nums, ans, used);
		
		return ans;
	}
	
	public static void backtrack(ArrayList<Integer> curr, int[] nums, ArrayList<ArrayList<Integer>> ans, boolean[] used){
		
		if(curr.size() == nums.length) {
			//curr는 참조변수이기 때문에 변경될 때마다 결과 리스트에 있는 모든 참조도 함께 변경
			//그걸 피하기 위해 객체를 새롭게 생성해서 넣어줘야함
			ans.add(new ArrayList<Integer>(curr));
			return;
		}
		
		for(int i=0; i<nums.length; i++) {
			if(!used[i]) {
				// 아직 사용되지 않은 원소인 경우 추가하고 재귀 호출
				used[i] = true;
				curr.add(nums[i]);
				backtrack(curr, nums, ans, used);
				// 재귀 호출이 끝나면 해당 원소를 다시 제거하고 다른 경우를 시도
				used[i] = false;
				curr.remove(curr.size()-1);
			}
		}
	}
	

	public static void main(String[] args) {
		//순열
		int[] nums = {1,2,3,4};
		
		ArrayList<ArrayList<Integer>> permutation = p(nums);
		
		for(ArrayList<Integer> per : permutation) {
			System.out.println(per);
		}
	}

}