中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

leetCode 46. Permutations 回溯問題 | Medium

發布時間:2020-07-05 02:09:45 來源:網絡 閱讀:739 作者:313119992 欄目:編程語言

46. Permutations(全排列問題--回溯問題經典)

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

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

題目大意:求一個序列的全排列。

思路:做排列組合時,模擬該過程得到思路。首先選擇集合中的某一個元素作為第一位,接著在剩下的元素中選擇一個元素作為第二位,一直到為空。
上述過程顯然是個遞歸的過程,聲明幫助函數:Helper(vector<vector<int> >& result, vector<int>& tmp, vector<int>& nums)。tmp用來存儲已經選定的元素,nums用來存儲剩下的元素,result存儲所得的情況。顯然當nums為空的時候遞歸應該返回。
注意:關鍵在于對nums和tmp的處理,一旦tmp中增加了一個元素,nums就要刪除該元素;每次有一個幫助函數返回時都會進行一次回溯,即nums要插入元素,tmp要刪除元素。

代碼如下:(采用典型的回溯來處理)

class Solution {
public:
    void permuteHelper(vector<vector<int> >& result,vector<int> &tmp,vector<int>& nums)
    {
        if(nums.empty())
        {
            result.push_back(tmp);
            return;
        }
        
        for(int i = 0; i < nums.size(); i++)
        {
            int val = nums[i];
            tmp.push_back(val);
            nums.erase(nums.begin()+i);
            permuteHelper(result,tmp,nums);
            nums.insert(nums.begin()+i,val);
            tmp.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> tmp;
        permuteHelper(result,tmp,nums);
        
        return result;
    }
};

2016-08-07 15:11:04

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

双桥区| 安化县| 孟村| 云和县| 射阳县| 巨野县| 青河县| 陇南市| 贺兰县| 资中县| 郑州市| 陆良县| 昭平县| 冀州市| 白玉县| 镇江市| 石阡县| 南京市| 吉木乃县| 贺州市| 大同市| 微山县| 和田市| 阿克苏市| 泗洪县| 韶关市| 松桃| 道孚县| 万山特区| 子长县| 清涧县| 开江县| 鄄城县| 马鞍山市| 准格尔旗| 彰化市| 灌阳县| 孙吴县| 玉门市| 湘阴县| 渝中区|