[Leetcode]46. Permutations(C++)

题目描述

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

例子

例子 1

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

例子 2

Input: nums = [0,1] Output: [[0,1],[1,0]]

例子 3

Input: nums = [1] Output: [[1]]

Follow Up

Note

Constraints

1 <= nums.length <= 6

-10 <= nums[i] <= 10

All the integers of nums are unique.

解题思路

这道题要求我们返回给定数组的所有组合，这道题和 [Leetcode]77. Combinations(C++) 的区别在于，由于求的是组合，因此每个元素组合可以出现不止一次（只需要相对位置不同即可）。因此在使用回溯的时候我们在为每个子集合选择下一个位置的元素不仅需要考虑当前索引后面的元素，只要数组中没被当前子集和选中的元素都是候选元素。表现在代码上的区别是：

combination 的遍历策略：传入当前子集合最新加入元素的索引，从该索引往后遍历每一个元素对每一个元素进行：添加-递归-删除操作；
permutation 的遍历策略：传入当前子集和所有包含的元素（以哈希表的形式），对数组中索引元素进行判断是否在子集和中，如果不是，则进行：添加-递归-删除操作

代码如下：

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        std::vector<int> perm;
        std::vector<std::vector<int>> result;
        std::vector<bool> visisted(nums.size(), false);
        iterate(nums, perm, result, visisted);
        return result;
    }

private:
    void iterate(const std::vector<int>& nums, std::vector<int> perm, std::vector<std::vector<int>>& result, std::vector<bool> visisted) {
        if (perm.size() == nums.size()) {
            result.push_back(perm);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (!visisted[i]) {
                perm.push_back(nums[i]);
                visisted[i] = true;
                iterate(nums, perm, result, visisted);
                perm.pop_back();
                visisted[i] = false;
            }
        }
    }
};

时间复杂度: O(2^n)
空间复杂度: O(2^n)

GitHub 代码同步地址： 46.Permutations.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions