046 全排列

题目

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

示例:

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

实现

第一种:回溯法(back tracking) 是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

白话:回溯法可以理解为通过选择不同的岔路口寻找目的地,一个岔路口一个岔路口的去尝试找到目的地。如果走错了路,继续返回来找到岔路口的另一条路,直到找到目的地。

本练习的回溯过程如下所示:

  • 状态:通过
  • 25 / 25 个通过测试用例
  • 执行用时: 364 ms, 在所有 C# 提交中击败了 80.00% 的用户
  • 内存消耗: 30.6 MB, 在所有 C# 提交中击败了 7.14% 的用户
public class Solution
{
    private IList<IList<int>> _result;
    private bool[] _used;

    public IList<IList<int>> Permute(int[] nums)
    {
        _result = new List<IList<int>>();
        if (nums == null || nums.Length == 0)
            return _result;
        _used = new bool[nums.Length];

        FindPath(nums, 0, new List<int>());
        return _result;
    }

    public void FindPath(int[] nums, int count, List<int> path)
    {
        if (count == nums.Length)
        {
            //递归终止条件
            List<int> item = new List<int>();
            item.AddRange(path);
            //加入拷贝
            _result.Add(item);
            return;
        }
        for (int i = 0; i < nums.Length; i++)
        {
            if (_used[i] == false)
            {
                path.Add(nums[i]);
                _used[i] = true;
                FindPath(nums, count + 1, path);
                path.RemoveAt(path.Count - 1);
                _used[i] = false;
            }
        }
    }
}
浙ICP备19012682号