例如#xff1a;0.1.2.201

其实本题与上一题很像都是用分割线在所给字符串里进行切割本题如果切割到255的情况就得终止以及题目要求中ip地址只有四段即出现三个逗号时就得终止

class

public:vectorstringresult;//由题本题返回的结果是由字符串组成的一维数组//判断是否为合法ip地址bool

isValid(const

(s[i]-0);//本题传入的数字是字符串类型要记得转成整型if(num

255)//非法{return

pointSum){//终止条件if(pointSum3){if(isValid(s,startIndex,s.size()-1)true){result.push_back(s);

return;}

istartIndex;is.size();i){if(isValid(s,startIndex,i)true)//判断子区间是否为有效{s.insert(s.begin()

.);

在i的后面插入一个逗点coutpointSum;pointSum;backtracking(s,i2,pointSum);//因为加了逗号占一个位置所以应该传入i2pointSum--;//回溯s.erase(s.begin()i1);//回溯}else{//不合法break;}}}​vectorstring

s.size()12)return

result;//剪枝backtracking(s,0,0);return

result;}

backtracking(s,i2,pointSum);这里的i是两个两个加

初始条件

输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入nums

由上图可知本题与之前的回溯问题最大的区别就是之前的回溯算法题收集的都是叶子节点但是本题收集的是除根结点外所有结点

class

public:vectorintpath;vectorvectorintresult;void

startIndex){result.push_back(path);//收集空集if(startIndexnums.size())//终止条件{return;}

​for(int

startIndex;inums.size();i){path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}vectorvectorint

subsets(vectorint

{path.clear();result.clear();backtracking(nums,0);return

result;}

public:vectorintpath;vectorvectorintresult;void

startIndex,vectorboolused){result.push_back(path);if(startIndexnums.size()){return;}for(int

istartIndex;inums.size();i){if(i0

nums[i]nums[i-1]

used[i-1]false)//相同元素会产生的结果已经收集过了{continue;}path.push_back(nums[i]);used[i]true;backtracking(nums,i1,used);used[i]false;//回溯path.pop_back();}}vectorvectorint

nums)

{path.clear();result.clear();vectorboolused(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,0,used);return

result;}