回溯法求解数组中和为固定值的所有元素集合

一、前言

       本文参考自http://blog.csdn.net/u012462822/article/details/51193689，找出数组中和为固定值的所有元素集合，常用的思路是先进行排序，之后再用回溯的方法不断尝试所有可能集合。以下先用快速排序(写得有点烂)降序，再找出降了序的数组中和为某值的所有元素集合

二、回溯法

      代码如下

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

void QSort(int * arr,int idxStart,int idxEnd)
{
   if (idxEnd<1||arr == NULL)  return;

   int key = arr[idxStart];

   int i = idxStart ;
   int j = idxEnd;

   while(j != i){
       while(j != i){
           if(arr[j]>key){
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                i++;
                break;
           }else{
                j--;
       	   }
       }

      while(j != i){
           if( arr[i] <=key){
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                j--;
                break;
           }else{
                i++;
           }
      }
   }

   if(i > 1){
      QSort(arr,0,i-1);
   }
   if(idxEnd-i > 1){
      QSort(arr,i+1,idxEnd);
   }

}

/*
    arr: 数组指针
    n: 数组长度
    beginIdx: 表示搜索的位置，初始为0
    currSums：存贮搜索元素的和，初始为0
    findT：固定值
    res：存储搜索的元素

*/
void BackTrack( int* arr  , int  n   ,  int beginIdx    ,   int currSums ,  int  findT  , vector< int > & res  )
 {
        if (  beginIdx >= n  ||    currSums > findT )  return; //判断搜索是否该结束

        currSums  +=arr[  beginIdx ] ;   //加入下标为beginIdx的元素
        res.push_back( arr[  beginIdx  ] );

        if( currSums ==  findT){   //判断当前搜索到的元素是否满足和为findT，满足则输出集合
                for(int i = 0 ; i <  res.size(); ++i)
                        cout<< res[i]  <<"   ";
                        cout<<"n";
        }

        BackTrack(    arr ,  n   , beginIdx+1 ,  currSums  ,    findT  ,   res     ) ;  //尝试找下一个
        res .pop_back();          //如果BackTrack发生return，说明如果加入beginIdx处的元素不满足要求
        currSums  -=arr[  beginIdx ] ;

        int j ;

        for(   j = beginIdx+1 ;  j <  n ;  ){  //跳过beginIdx之后可能相同的元素
                if(  arr[j] ==arr[  beginIdx ]  ){
                        j++;
                }else{
                        break;
                }

        }

        BackTrack(  arr ,  n    ,  j ,     currSums    ,    findT     ,   res); //在J后重新搜索

 }


int main()
{

        int  arr[] = { 6 , 202 , 88,  -102 ,   100 , 41,  12  ,  23 ,   34  ,  25 ,  50, 41 , 11 };
        int n =  13 ;

        QSort(    arr    ,    0 ,     n -1 );
        cout<<"排序后n";
        for(int i = 0 ; i < n ; ++i){
                cout<<  arr[i] <<  "  "  ;
        }

        vector< int >  path ;
        int findT = 100;
        int beginIdx = 0;
        int currSums = 0;

        cout<<"nn和为" <<findT<<"的元素集合为：n";
        BackTrack(   arr    , n   ,   beginIdx    ,   currSums ,   findT  , path  ) ;

}

三、运行结果

最后

以上就是爱撒娇季节为你收集整理的回溯法求解数组中和为固定值的所有元素集合的全部内容，希望文章能够帮你解决回溯法求解数组中和为固定值的所有元素集合所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。