LeetCode Permutations

原題鏈接在這里：https://leetcode.com/problems/permutations/

題目：

Given a collection of?distinct?numbers, return all possible permutations.

For example,
[1,2,3]?have the following permutations:
[1,2,3],?[1,3,2],?[2,1,3],?[2,3,1],?[3,1,2], and?[3,2,1].

題解：

與Combinations相似，都是NP問題可以采用遞歸加回朔，遞歸的終止條件與Combinations相同，item.size()滿足要求就把item加到res里。

這里采用boolean [] used數組來代表當前數是否被用過。若是被用過就跳過，沒有被用過把nums[i]加到item中，然后遞歸剩下的元素。

當遞歸結束后，減掉item尾部元素，同時需要維護used數組，把當前位置變回false, 確保進入遞歸和結束遞歸時狀態相同。

Time Complexity: exponential.

AC Java:

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0){
            return res;
        }
        boolean [] used = new boolean[nums.length];
        helper(nums,used,new ArrayList<Integer>(), res);
        return res;
    }
    private void helper(int[] nums, boolean [] used, List<Integer> item, List<List<Integer>> res){
        if(item.size() == nums.length){
            res.add(new ArrayList<Integer>(item));
            return;
        }
        for(int i = 0; i<nums.length; i++){
            if(!used[i]){
                used[i] = true;
                item.add(nums[i]);
                helper(nums,used,item,res);
                item.remove(item.size()-1);
                used[i] = false;
            }
        }
    }
}

這道題的迭代方法如下：

與Subsets相似，開始時item先加nums[0], 把item加到res里.

然后每次添加新的nums[i], 首先把res里的每一個item拿出來, 用cur表示.

在cur的所有可能位置加上新的元素nums[i], 然后把它加載回res里。

Note: res原有的item不能保留，所以每次掃描res所有item前新建newRes, 添加完新元素nums[i]的item是要加到newRes中去的，所有可能的item都加完后再把newRes賦值回res去。

Time Complexity: exponential.

AC Java:

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums == null || nums.length == 0){
            return res;
        }
        List<Integer> item = new ArrayList<Integer>();
        item.add(nums[0]);
        res.add(item);
        
        for(int i = 1; i<nums.length; i++){
            List<List<Integer>> newRes = new ArrayList<List<Integer>>();
            for(int j = 0; j<res.size(); j++){
                List<Integer> cur = res.get(j);
                for(int k = 0; k<=cur.size(); k++){
                    // 記得這里要做個copy, 不能直接在原來的cur上加
                    item = new ArrayList<Integer>(cur);
                    item.add(k, nums[i]);
                    newRes.add(item);
                }
            }
            res = newRes;
        }
        return res;
    }
}

跟上Permutations II.