46. 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],
  [3,2,1]
]

Solution：Backtracking

总结见：http://www.jianshu.com/p/883fdda93a66
思路：
backtracking的基本套路，要注意的是：
因为是排列问题，所以"for next可能"的时候不从start开始，需要要从0开始并设立used数组以免重复访问
Time Complexity: O(N!) Space Complexity: O(N)

Solution Code：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> cur_res = new ArrayList<>();
        
        // Arrays.sort(nums); // not necessary
        boolean[] used = new boolean[nums.length];
        
        backtrack(nums, used, cur_res, result);
        return result;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> cur_res, List<List<Integer>> result) {
        if(cur_res.size() == nums.length){
            result.add(new ArrayList<>(cur_res));
            return;
        }
        
        for(int i = 0; i < nums.length; i++){ 
            if(used[i]) continue; // element already exists, skip
            cur_res.add(nums[i]);
            used[i] = true;
            backtrack(nums, used, cur_res, result);
            cur_res.remove(cur_res.size() - 1);
            used[i] = false;
        }
    } 
}