leetcode-solutions/46.permutations.cpp at master · Raees678/leetcode-solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
 * @lc app=leetcode id=46 lang=cpp
 *
 * [46] Permutations
 *
 * https://leetcode.com/problems/permutations/description/
 *
 * algorithms
 * Medium (51.05%)
 * Likes:    2717
 * Dislikes: 88
 * Total Accepted:    473.1K
 * Total Submissions: 804.8K
 * Testcase Example:  '[1,2,3]'
 *
 * Given a collection of distinct integers, return all possible permutations.
 *
 * Example:
 *
 *
 * Input: [1,2,3]
 * Output:
 * [
 * ⁠ [1,2,3],
 * ⁠ [1,3,2],
 * ⁠ [2,1,3],
 * ⁠ [2,3,1],
 * ⁠ [3,1,2],
 * ⁠ [3,2,1]
 * ]
 *
 *
 */

// @lc code=start
class Solution {
 public:
  void permuteHelper(vector<int>& nums, vector<bool>& number_used,
                     vector<int>& buffer, int buffer_index,
                     vector<vector<int>>& return_vector) {
    if (buffer_index == nums.size()) {
      return_vector.push_back(buffer);
      return;
    }

    for (int i = 0; i < nums.size(); ++i) {
      if (!number_used[i]) {
        buffer[buffer_index] = nums[i];
        number_used[i] = true;
        permuteHelper(nums, number_used, buffer, buffer_index + 1,
                      return_vector);
        number_used[i] = false;
      }
    }
  }

  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> return_vector;
    vector<int> buffer(nums.size(), 0);
    vector<bool> number_used(nums.size(), false);
    permuteHelper(nums, number_used, buffer, 0, return_vector);
    return return_vector;
  }
};
// @lc code=end