46. Permutations

Leetcode Backtracking

题目

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]
]

分析

典型的回溯法，需要注意的地方:

• base case时，不能使用list.add(chosen)，必须返回chosen的深拷贝。因为chosen会被修改。

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    if (nums == null || nums.length == 0) return list;
    LinkedList<Integer> chosen = new LinkedList<>(), numbers = new LinkedList<>();
    for (int n : nums) numbers.add(n);
    permuate(list, numbers, chosen);
    return list;
}

private void permuate(List<List<Integer>> list, LinkedList<Integer> nums, LinkedList<Integer> chosen) {
    // base case
    if (nums.size() == 0)  list.add(new ArrayList<Integer>(chosen));
    for (int i = 0; i < nums.size(); i++) {
        Integer n = nums.remove(i);
        chosen.addLast(n);                  // chosen
        permuate(list, nums, chosen);       // explore
        nums.add(i, n);                     // unchosen
        chosen.removeLast();
    }
}

Cpp

典型的backtracking题目，非常简单。

class Solution {
public:
    void permuteHelper(vector<vector<int>> &result, vector<int>& nums, vector<int>& chosen){
        if (nums.size()==0){
            result.push_back(chosen);
        }else{
            for (vector<int>::iterator iter=nums.begin(); iter!=nums.end(); iter++){
                //choose
                int s = *iter;
                chosen.push_back(s);
                nums.erase(iter);

                //explore
                permuteHelper(result, nums, chosen);

                //unchoose
                chosen.pop_back();
                nums.insert(iter, s);
            }
        }
    }


    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> chosen;
        vector<vector<int>> result;
        permuteHelper(result, nums, chosen); 
        return result;
    }
};

还有没有其他方法呢？我们求一组数字的排列，可以看成两步：⾸先求所有可能出现在第⼀个位置的数字，即把第⼀个数字和后⾯所有的数字交换。即⾸先固定第⼀个数字，求后⾯所有数字的排列。这个时候我们仍把后⾯ 的所有数字分成两部分：后⾯数字的第⼀个数字，以及这个数字之后的所有数字。然后把第⼀个数字逐⼀和它后⾯的字符交换。

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    if (nums == null || nums.length == 0) return list;
    permute(list, nums, 0);
    return list;
}

private void permute(List<List<Integer>> list, int[] nums, int index) {
    // base case
    if (nums.length - 1 == index) {
        constructList(list, nums);
        return;
    }
    permute(list, nums, index + 1);
    int tmp = nums[index];
    for (int i = index + 1; i < nums.length; i++) {
        nums[index] = nums[i];
        nums[i] = tmp;
        permute(list, nums, index + 1);
        nums[i] = nums[index];
        nums[index] = tmp;
    }
}

private void constructList(List<List<Integer>> list, int[] nums) {
    ArrayList<Integer> numsList = new ArrayList<>();
    for (int n : nums) numsList.add(n);
    list.add(numsList);
}