#LeetCode:46. Permutations

利用遞迴將每個位置去決定要放的值,每次決定好後就將該值與目前的值做交換繼續遞迴下去,遞迴回來後就復原再將下一個值與目前的值交換繼續遞迴下去。

參考 LeetCode 論壇的解答

C++(12ms)

/*******************************************************/
/* LeetCode 46. Permutations                           */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2019/04/11                                 */
/*******************************************************/
#include <vector>
using namespace std;

class Solution {
public:
  void recursivePermute(vector<vector<int>> &answer, vector<int> &nums, int index){
    if(index >= nums.size()) {
      answer.push_back(nums);
      return;
    }

    for(int i = index ; i < nums.size() ; ++i){
      swap(nums[i], nums[index]);
      recursivePermute(answer, nums, index + 1);
      swap(nums[i], nums[index]);
    }
  }

  vector<vector<int>> permute(vector<int>& nums) {
    if(nums.size() == 0) return vector<vector<int>>();
    vector<vector<int>> answer;
    recursivePermute(answer, nums, 0);
    return answer;
  }
};

回應

目前無留言,歡迎留言!

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: