字符串的排列

全排列算法的思路大概是我们可以把一个字符串看成由两部分组成：一部分分为它的第一个字符，第二部分是后面的所有字符。

46.全排列

题目：

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例：

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路：

• 1、我们把整个字符串的排列分为两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。（比如现在第一个字符是1，初始序列为[1,2,3]。然后把1和2交换得到[2,1,3]。最后1和3交换得到序列为[3,2,1]）
• 2、第二步就是固定第一个字符，求后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一字符逐一和它后面的字符交换。

Permutations

package com.zhoujian.solutions.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author zhoujian123@hotmail.com 2018/8/17 15:35
 */
public class Permutation {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        // Arrays.sort(nums); // not necessary
        backtrack(list, new ArrayList<Integer>(), nums);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
        if(tempList.size() == nums.length){
            list.add(new ArrayList<Integer>(tempList));
        } else{
            for(int i = 0; i < nums.length; i++){
                if(tempList.contains(nums[i])) continue; // element already exists, skip
                tempList.add(nums[i]);
                backtrack(list, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
//        int[] nums = {1,2,3};
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] s = line.split(" ");
        int[] nums = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            nums[i] = Integer.parseInt(s[i]);
        }
        Permutation permutation = new Permutation();
        List<List<Integer>> listList = permutation.permute(nums);
        System.out.println(listList);
    }
}

结果如下：

image.png

扩展题

如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？还是输入三个字符a、b、c，则它们的组合有a、b、c、ab、ac、bc、abc。当交换字符串中的两个字符时，虽然能得到两个不同的排列，但却是同一个组合。比如ab和ba是不同的排列，但只算一个组合。