문제

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

제한사항

• 1 $\leq$ nums.length $\leq$ 6
• -10 $\leq$ nums[i] $\leq$ 10
• All the integers of nums are unique.

접근

주어진 배열로 구성할 수 있는 순열Permutation을 모두 반환하는 문제에요. C++에 제공되나, Java는 따로 API가 존재하지 않아요. 그래서 만들어줘야 해요. 순열에 대한 로직은 Next Permutation에 잘 정리했으니 참고해주세요 ㅎㅎ.

순열의 개수는 (배열의 길이)!에요. 그래서 처음에 원본 배열을 추가하고, (배열의 길이)! - 1만큼 전개를 시켜서 답을 도출했어요.

답안

class Solution {
    
    public List<List<Integer>> permute(int[] nums) {        
        List<List<Integer>> answer = new ArrayList<>();
        
        answer.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
        for(int i = 0; i < getFactorial(nums.length) - 1; ++i){
            List<Integer> lastElement = answer.get(answer.size() - 1);
            List<Integer> candidate = getNextPermutation(lastElement);
            answer.add(candidate);
        }

        return answer;
    }

    private List<Integer> getNextPermutation(List<Integer> nums){
        List<Integer> ret = new ArrayList<>();
        ret.addAll(nums);

        int i = nums.size() - 2;
        while(0 <= i && nums.get(i + 1) <= nums.get(i)){
            --i;
        }
        
        if(0 <= i){
            int j = nums.size() - 1;
            while(nums.get(i) >= nums.get(j)){
                --j;
            }
            Collections.swap(ret, i, j);
        }
        reverse(ret, i + 1);

        return ret;
    }

    private void reverse(List<Integer> list, int start){
        int i = start;
        int j = list.size() - 1;
        while(i < j){
            Collections.swap(list, i, j);
            i++;
            j--;
        }
    }

    private int getFactorial(int num){
        if(num <= 1){
            return 1;
        }
        return num * getFactorial(num - 1);
    }

}