46. Permutations.md

46. Permutations

Question:

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Thinking:

1. Traceback

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null && nums.length == 0)
            return result;
        traceback(nums, result, new ArrayList<Integer>());
        return result;
    }
    public static void traceback(int[] nums, List<List<Integer>> result, List<Integer> list){
        if(list.size() == nums.length)
            result.add(new ArrayList<Integer>(list));
        else{
            for(int i = 0; i < nums.length; i++){
                if(!list.contains(nums[i])){
                    list.add(nums[i]);
                    traceback(nums, result, list);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
}

二刷

1. 这种回溯的题目还是比较有套路的。这次用布尔数组替换了hashSet，应该会快一些。

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

Third time

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if(nums.length == 0) return result;
        dfs(result, nums, new boolean[nums.length], new LinkedList<>());
        return result;
    }
    private void dfs(List<List<Integer>> result, int[] nums, boolean[] visited, List<Integer> temp){
        if(temp.size() == nums.length) result.add(new LinkedList<Integer>(temp));
        else{
            for(int i = 0; i < nums.length; i++){
                if(visited[i]) continue;
                visited[i] = true;
                temp.add(nums[i]);
                dfs(result, nums, visited, temp);
                temp.remove(temp.size() - 1);
                visited[i] = false;
            }
        }
    }
}

C++ Version

• Method 1:

   class Solution {
   	vector<vector<int>> res_;
   	void dfs(int begin, int size, vector<int>& nums){
   		if(begin >= size){
   			res_.push_back(nums);
   			return;
   		}else{
   			for(int i = begin; i < size; ++i){
   				swap(nums[begin], nums[i]);
   				dfs(begin + 1, size, nums);
   				swap(nums[begin], nums[i]);
   			}
   		}
   	}
   public:
   	vector<vector<int>> permute(vector<int>& nums) {
   		dfs(0, nums.size(), nums);
   		return res_;
   	}
   };