곱셈에서subset 문제풀이로의 곱셈 사상 확장

제목: LintCode/LeetCode

            ，        .   S = [1,2,3]，     ：
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

서로 다른 원소가 집합된 모든 서브집 문제를 구하려면 인터넷에 각종 참고 코드가 있지만 코드에서 작가의 사고방식을 거꾸로 생각하기는 매우 어렵다.그래서 나는 코드는 사람들에게 보여주는 것이어야 하며 코드의 간결함을 지나치게 추구해서는 안 된다고 생각해 왔다.
서브셋을 구하는 문제에 대해 인터넷상에서 AC의 답이 매우 많고 문제를 푸는 방법은 대략 세 가지가 있다(추쿠링크).그중의 귀속해법 코드에 대해 나는 오랫동안 보았지만 요령부득이어서 버리고 돌아서서 스스로 생각해 보았다.
스스로 일주일 동안 독립적으로 생각하고 곱셈의 기본적인 귀속 조작에서 한 걸음 한 걸음 본 문제의 해법을 제시했다.그래서 본고를 쓰는 목적은 더 많은 사람들이 가장 기본적인 곱셈의 귀환에서 구자집의 귀환을 완성하도록 돕는 것이다.

역귀사상의 깊이 있는 응용

우선, 우리는 n의 계승을 구하는데, 매우 간단하다.

int myFun(int n){
    if( n == 1 || n == 0){          //    
        return 1;
    }
    //               
    int lastResult = myFun(n-1);
    return n * lashResult ;     

}

귀착에는 몇 가지 요소가 있다.종료 조건 2.매개 변수 변화점차적인 공식에 대응하는 것은 계승에서 각각 1이다.n은 1 또는 0 2.n매번 1, 3.(n의 곱하기) = n*(n-1의 곱하기)
그리고 우리는 다시 구자집 문제를 생각하러 간다.

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

 123        ：[1,2]           3，      [1,2]。
     ：                       。
   ：
 10        ：9     10
     ： 9         10   。

[1,2,3]의 서브집합을 구하기 위해 우리는 [1,2]의 서브집합을 요구하고 [1,2]의 서브집합을 구하기 위해 [1]의 서브집합을 요구한다. 이렇게 끊임없이 서브집합을 깊이 있게 축소하여 집합에 하나의 원소만 남을 때까지 해야 한다. 이때 [1]의 서브집합은 [[[[1],[1](공집합과 1 자체)만 있고 이때도 퇴출 조건에 도달한다. 서브집합은 [1]의 서브집합을 가지고 돌아오고 [1,2]의 서브집합, [1,2]의 서브집합, [1,2]의 서브집합을 차례로 계산한다.
서브집합의 귀속을 구하는 요소: 1.종료 조건: 원본 집합 원소의 개수가 1, 2이면매개 변수 변화: 서브집합의 원본 집합을 구하여 순서대로 1개의 원소를 축소한다.추이 공식: [1,2,3]의 서브집합은 [1,2]의 각 서브집합에 3을 첨가한 다음에 원[1,2]의 서브집합을 합친다.
따라서 코드는 n의 곱하기와 유사하다.

//source: vector<int> [1,2,3]
//ind : source   
//call : subsetHelper(source, source.size()-1)
vector<vector<int>> subsetHelper(vector<int>& source, int ind){

    vector<int> subset;
    vector<vector<int>> result;

    //    ：                 
    if (ind == 0) {
        subset.push_back(source[0]);//self
        result.push_back(subset);   //null set
        result.push_back(subset);
        return result;
    }


    //    ：ind-1                  
    result = subsetHelper(source, ind - 1);


    //    ：                 
    vector<vector<int>> ori = result;

    //      1： [1,2]       3
    int i = 0;
    for ( i = 0; i < result.size(); i++) {
        result[i].push_back(source[ind]);
    }

    //      2： [1,2]     3      
    result.insert(result.end(), ori.begin(), ori.end());

    return result;

}

코드가 뚜렷하고 읽기 쉽도록 위에서 가장 원시적인 코드입니다.다음은 정리된 코드입니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


void subsetHelper(vector<int>& source, int ind, vector<vector<int>>& result){

    vector<int> subset;
    //1.   ：          
    //2. ［1，2］        ［3］
    //3. ［1，2］     3       

    //1
    if (ind == 0) {
        result.push_back(subset);   //add null set
        subset.push_back(source[0]);
        result.push_back(subset);
        return ;
    }

    subsetHelper(source, ind - 1, result);

    vector<vector<int>> ori = result;//    

    //2
    int i = 0;
    for ( i = 0; i < result.size(); i++) {
        result[i].push_back(source[ind]);
    }

    //3
    result.insert(result.end(), ori.begin(), ori.end());

}

int main()
{
    vector<int> source;
    source.push_back(1);
    source.push_back(2);
    source.push_back(3);
    vector<vector<int>> result;

    // [1,2,3]   
    subsetHelper(source, (int)source.size() -1, result);

    //    
    for (int j = 0; j < result.size(); j++) {
        for (int i = 0; i < result[j].size(); i++) {
            cout<<result[j][i];
        }
        cout<<endl;
    }

    return 0;
}

생각이 아직 다하지 않았느냐?해법