15. 전체 배열

묘사
숫자 목록을 정해서 가능한 모든 배열을 되돌려줍니다.
주의사항
너는 중복 숫자가 없다고 가정할 수 있다.
예제
목록[1,2,2]을 제시하고 서로 다른 배열은 다음과 같다.

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

도전하다
귀속과 비귀속을 사용하여 각각 이 문제를 완성하다.

코드

귀속

public class Solution {
    public List> permute(int[] nums) {
        List> results = new ArrayList<>();
        // ， [], [[]]
        if (nums == null) {
            return results;
        }
        if (nums.length == 0) {
            //List ， ， ArrayList
            results.add(new ArrayList());
            return results;
        }
        
        List list = new ArrayList<>();
        helper(nums, list, results);
        return results;
    }
    
    private void helper(int[] nums,
                        List list,
                        List> results) {
        // 
        //  [ ](https://www.jianshu.com/p/b494dde0ffdb) ，
        //   startIndex   +1，startIndex >= nums.length  
        if (list.size() == nums.length) {
            results.add(new ArrayList(list));
            return;
        }
        // ， ， 
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            helper(nums, list, results);
            list.remove(list.size() - 1);
        }
    }
}

비귀속

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List> permute(int[] nums) {
        ArrayList> permutations
             = new ArrayList>();
        if (nums == null) {
            
            return permutations;
        }

        if (nums.length == 0) {
            permutations.add(new ArrayList());
            return permutations;
        }
        
        int n = nums.length;
        ArrayList stack = new ArrayList();
        
        stack.add(-1);
        while (stack.size() != 0) {
            Integer last = stack.get(stack.size() - 1);
            stack.remove(stack.size() - 1);
            
            // increase the last number
            int next = -1;
            for (int i = last + 1; i < n; i++) {
                if (!stack.contains(i)) {
                    next = i;
                    break;
                }
            }
            if (next == -1) {
                continue;
            }
            
            // generate the next permutation
            stack.add(next);
            for (int i = 0; i < n; i++) {
                if (!stack.contains(i)) {
                    stack.add(i);
                }
            }
            
            // copy to permutations set
            ArrayList permutation = new ArrayList();
            for (int i = 0; i < n; i++) {
                permutation.add(nums[stack.get(i)]);
            }
            permutations.add(permutation);
        }
        
        return permutations;
    }
}

본제 귀속 과정
DFS의 관건은 for순환에 귀속되는 변화 과정을 이해하는 데 있다. 본고[1,2,3]를 예로 들면 첫 번째 for순환 시 1을 list,list[1]에 넣고 프로그램이 helper(rst,list,nums)로 실행될 때 두 번째 층으로 귀속한다. for순환은 1,continue,for순환은 2, 2를 list,list[1,2]에 넣고 프로그램이 다시 helper(rst,list,nums)로 실행될 때 세 번째 층으로 귀속한다. for순환은 1, 2,list에 1,2,continue가 존재하고 for는 3까지 순환하며 3을list에 넣고 4층으로 귀속합니다. 이때list.size () =num.length,list를rst에 추가하고return 문장은 4층 귀속을 직접 종료합니다(지금까지 4층 귀속을 실행했지만 프로그램의 마지막 문장을 실행하지 않았습니다). 4층 귀속을 종료한 후 3층 귀속의 마지막 문장을 실행하고list에서 마지막 요소를 삭제합니다. 이때 3층 for순환은 i=2까지 실행되었습니다.list를 실행합니다.remove(list.size()-1)는 3층 귀속이 전체적으로 끝난 셈이다. 3층 귀속을 종료한다. 이때list는[1,2]이고 2층 귀속을 시작한다. 이때 2층 귀속의 i=1, for 순환이 끝나지 않았고list를 끝낸다.remove(list.size()-1)가 되면list는 [1]로 변하고 for 순환 중 i는 2,nums[2]=3을 list에 첨가하고list는 [1,3]로 helper(rst,list,nums)를 계속 집행하며 다시 다섯 번째 귀환에 들어간다.list 중 1,continue,for 순환에서 2(i=1)로 2를 추가하고 다음 층의 여섯 번째 귀환으로 들어가 수출 조건을 만족시킨다.return,이 층의 여섯 번째 귀환이 끝나고 다섯 번째 귀환에서 for 순환 중 i=1의 마지막 문장 목록으로 돌아간다.remove(list.size()-1),list에서 2를 제거하여list를 [1,3,2]에서 [1,3]로 바꾸어 for순환 i=2를 실행하기 시작하고list에 3,continue가 존재하는 것을 발견하고 for순환을 끝내고 다섯 번째 귀속을 다시 두 번째 귀속으로 들어가며 두 번째 귀속도 for순환 i=2의 마지막 문장으로 실행합니다.remove(list.size()-1)는list를[1]로 만든 후 2층 귀속을 종료하고 1층 귀속 for순환 중 i=0의 마지막 list를 실행합니다.remove(list.size()-1)는 list를 빈 집합으로 만들고 for 순환 i=1을 실행하고,list는 [2]가 된 후 귀속list는 [2,1], 귀속[2,1,3] 다음 과정은 이전 설명 과정과 유사합니다
총결산
본제와 서브집합 문제는 기본적으로 하나의 체계이다. 세부적으로 본고는 startIndex를 정의하여 순환의 시작 위치를 제한하지 않고 배열의 목적을 실현했다