LeetCode 46. Permutations [Medium] [C++] 解題筆記

Given a collection of distinct integers, return all possible permutations.

EX:

        Input: [1,2,3]

    Output:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

想法:

        這題是典型的 DFS 題目，因為元素並不會重複因此直接用 DFS 搜索所有排列即可。        

Complexity: O(n!) time

完整程式碼:

class Solution {

public:

    vector<vector<int>> ans;

    

    void dfs(vector<int>& nums, vector<bool>& use, vector<int>& cur) {

        if (cur.size() == nums.size()) {

            ans.push_back(cur);

            return;

        }

        

        for (int i = 0; i < nums.size(); i++) {

            if (use[i]) { continue; }

            use[i] = true;

            cur.push_back(nums[i]);

            dfs(nums, use, cur);

            use[i] = false;

            cur.pop_back();

        }

        return;

    }

    vector<vector<int>> permute(vector<int>& nums) {

        vector<bool> use(nums.size(), false);

        vector<int> cur;

        dfs(nums, use, cur);

        return ans;

    }

};