[LintCode] 15 Permutations 解题报告

Description
Given a list of numbers, return all possible permutations.

Notice
You can assume that there is no duplicate numbers in the list.


Example
For nums = [1, 2, 3], the permutations are:

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

Challenge
Do it without recursion.


思路
和Subsets这题差不多，都是套模版。
这题中，可以放进result的条件是list的长度等于nums的长度，说明每一个数都放进去了。
在每一层递归里，判断新的候选数字是不是已经在list里。如果已经在里面了，就continue掉。反之我们把这个数字放进list，并进入下一层递归查找。


Code

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
        // write your code here
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        
        if (nums == null || nums.length == 0) {
            result.add(list);
            return result;
        }
        
        search(nums, list, result);
        return result;
    }
    
    public void search( int[] nums, 
                        List<Integer> list, 
                        List<List<Integer>> result) {
                            
        if (list.size() == nums.length) {
            result.add(new ArrayList(list));
        }                    
                
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])) {
                continue;
            }
            list.add(nums[i]);
            search(nums, list, result);
            list.remove(list.size() - 1);
        }
        
        return;
    }
}