LeetCode46 Permutations 解题报告

By | 19/03/2018

【题目】:

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

意思就是说给n个不一样的正整数然后他们全排列的结果输出

【Code】:

class Solution {

public:

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

vector<vector<int> > res;

per(nums,0,res);

return res;

 

}

voidper(vector<int>&nums,int pos,vector<vector<int>>& res)

{

if(pos==nums.size())

{

res.push_back(nums);

return ;

}

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

{

swap(nums[i],nums[pos]);

per(nums,pos+1,res);

swap(nums[i],nums[pos]);//backtracking

}

}

};

【遇到的问题以及解决方法】:

首先我们看一下for循环的作用这个地方的for循环是为了增加广度,而递归了是为了增加深度,还有很重要的一点也是这个地方的很重要的问题就是我们如果说一为了得到某一个特定的排列则可以考虑一直递归到那个地步但是现在我们要求的是全部每一种请款都要输出,所以这个就非常的难受了,因为单纯的递归不管用了,所以需要回溯,这个是回溯的基本思想:在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。那么这个地方的回溯条件是什么,很简单,我们看我们需要做到的回溯就是返回到上一节点那么怎么从上一个节点到下一个节点的呢?我们是交换了两个节点,所以这一次我们进行同一个操作即可返回上一个节点,然后每一次当交换的位置到了最后一位的时候就不用再继续下去了然后就可以储存在容器当中。

发表评论