全排列

来源Leetcode第46题全排列

回溯1

要求生成给定数组的全排列，可采用回溯。

代码如下：

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        nextPer(nums,0);
        return ans;
    }
        private void nextPer(int[] arr,int start){
            //当start==arr.length-1时，说明子序列的长度为1，就不用再往下分子序列了
            if(start==arr.length-1){
                List<Integer> temp_ans = new ArrayList<>();
                for(int i = 0 ; i < arr.length ; i++){
                    temp_ans.add(arr[i]);
                }
                //System.out.println(temp_ans);
                ans.add(temp_ans);
				return ;
            }
            for(int i=start;i<arr.length;i++){
                //start代表的是每一个子序列的第一个位置，我们每一层递归的任务都只有一个：
                //枚举该层子序列第一个位置可以取的值
                int temp=arr[start];
                arr[start]=arr[i];
                arr[i]=temp;

                //该层递归的子序列第一个位置已经确定了，所以又可以往下再分
                nextPer(arr,start+1);

                //把第该层子序列第一个位置的值换成另外一个值，所以要交换回来
                temp=arr[start];
                arr[start]=arr[i];
                arr[i]=temp;
            }
        }
}

---

2019年10月30日更新：

回溯2

来自题解的回溯

这里有一个回溯函数，使用第一个整数的索引作为参数 backtrack(first)。

• 如果第一个整数有索引 n，意味着当前排列已完成。
• 遍历索引 first 到索引 n - 1 的所有整数。
  • 在排列中放置第 i 个整数，即 swap(nums[first], nums[i]).
  • 继续生成从第 i 个整数开始的所有排列: backtrack(first + 1).
  • 现在回溯，即通过 swap(nums[first], nums[i]) 还原.

代码如下：

class Solution {
  public void backtrack(int n,
                        ArrayList<Integer> nums,
                        List<List<Integer>> output,
                        int first) {
    // 如果所有的整数都参与排列了
    if (first == n)
      output.add(new ArrayList<Integer>(nums));
	//开始遍历索引first到索n-1的所有整数。
    for (int i = first; i < n; i++) {
      // 在当前的一种排列中，交换第i个元素和first元素的位置
      Collections.swap(nums, first, i);
      // 用下一个整数进行回溯生成排列
      backtrack(n, nums, output, first + 1);
      // 恢复交换的两个元素
      Collections.swap(nums, first, i);
    }
  }

  public List<List<Integer>> permute(int[] nums) {
  
    List<List<Integer>> output = new LinkedList();

    //将数组转化成列表
    ArrayList<Integer> nums_lst = new ArrayList<Integer>();
    for (int num : nums)
      nums_lst.add(num);
    int n = nums.length;
    backtrack(n, nums_lst, output, 0);
    return output;
  }
}