[Leetcode][Java] 46 Permutations (순열)

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

각각 다른 숫자가 포함된 배열이 주어진다.

가능한 모든 순열을 반환하라.

어떠한 순서로든 가능하다.

---

가능한 모든 순열을 반환하는 문제이다.

Backtracking을 통해서 가능한 모든 조합을 탐색해 보도록 하자.

 

조건이 만족해서, 결과 list에 추가되는 부분

더 탐색할 하위 노드가 남아 하위 노드로 이동하는 부분으로 코드를 구분할 수 있다.

    public void backtracking(List<List<Integer>> rst, int[] nums, List<Integer> list) {
        if (list.size() == nums.length) { // 조건이 만족 하는지 확인
            rst.add(new ArrayList<>(list));
            return;
        }

        for (int i : nums) { // 더 탐색할 하위 노드 탐색
            if (!list.contains(i)) {
                list.add(i);
                backtracking(rst, nums, list);
                list.remove(list.size() - 1);
            }
        }
    }

 

그럼 다음으로 해당 코드를 호출해주는 부분을 살펴 보자.

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();

        backtracking(rst, nums, new ArrayList<Integer>());
        return rst;
    }

 

 

출처 : https://leetcode.com/problems/permutations/

Permutations - LeetCode