46. Permutations（全排列問(wèn)題--回溯問(wèn)題經(jīng)典）

在虎林等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專(zhuān)注、極致的服務(wù)理念，為客戶(hù)提供成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì) 網(wǎng)站設(shè)計(jì)制作定制網(wǎng)站開(kāi)發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),全網(wǎng)整合營(yíng)銷(xiāo)推廣,外貿(mào)網(wǎng)站建設(shè),虎林網(wǎng)站建設(shè)費(fèi)用合理。

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]
]

題目大意：求一個(gè)序列的全排列。

思路：做排列組合時(shí)，模擬該過(guò)程得到思路。首先選擇集合中的某一個(gè)元素作為第一位，接著在剩下的元素中選擇一個(gè)元素作為第二位，一直到為空。
上述過(guò)程顯然是個(gè)遞歸的過(guò)程，聲明幫助函數(shù)：Helper(vector >& result, vector& tmp, vector& nums)。tmp用來(lái)存儲(chǔ)已經(jīng)選定的元素，nums用來(lái)存儲(chǔ)剩下的元素，result存儲(chǔ)所得的情況。顯然當(dāng)nums為空的時(shí)候遞歸應(yīng)該返回。
注意：關(guān)鍵在于對(duì)nums和tmp的處理，一旦tmp中增加了一個(gè)元素，nums就要?jiǎng)h除該元素；每次有一個(gè)幫助函數(shù)返回時(shí)都會(huì)進(jìn)行一次回溯，即nums要插入元素，tmp要?jiǎng)h除元素。

代碼如下：(采用典型的回溯來(lái)處理)

class Solution {
public:
    void permuteHelper(vector >& result,vector &tmp,vector& 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> permute(vector& nums) {
        vector> result;
        vector tmp;
        permuteHelper(result,tmp,nums);
        
        return result;
    }
};

2016-08-07 15:11:04