서브 집합 문제 알고리즘 분석 과 실현 (재 귀, 비 재 귀)

질문 설명:
숫자 집합 {1, 2, 3} 이 있 으 면 그 부분 집합 은 NULL, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 이다.현재 주어진 배열 은 모든 부분 집합 을 구 합 니 다.
다음 과 같이 구현:

//   
//{1，2，3}
// 0 0 0
// 0 0 1
// 0 1 0
// 0 1 1
// 1 0 0
// 1 0 1
// 1 1 0
// 1 1 1
//       ， 2       
//    
//        
class Solution
{
public:
    void subset(int *value, int size)
    {
        if (value == NULL || size < 1) return;//     

        int *tmp = (int *)malloc(size * sizeof(int));//          
        assert(tmp != NULL);
        memset(tmp, 0, size*sizeof(int));

        int num = (int)pow((double)2, (double)size);//      
        cout << "NULL" << endl;
        for (int i = 1; i < num; ++i)
        {
            for (int j = 0; j < size; ++j)//       ，     
            {
                if (tmp[j] == 1) tmp[j] = 0;//    
                else if (tmp[j] == 0)
                {
                    tmp[j] = 1;
                    break;
                }
            }
            for (int j = 0; j < size; ++j)//      ，         
            {
                if (tmp[j] == 1) cout << value[j] << " ";
            }
            cout << endl;
        }
        delete tmp;//      
    }
};

//  
class Solution
{
public:
    int *tmp;//         
    void createArray(int size)//      
    {
        tmp = (int *)malloc(size * sizeof(int));
        assert(tmp != NULL);
        memset(tmp, 0, size * sizeof(int));
    }
    void deleteArray()//      
    {
        free(tmp);
    }
    void subsetRecursive(int *value, int m, int size)
    {
        if (m == -1)//         ，      
        {
            for (int i = size - 1; i >= 0; --i)
            {
                if (tmp[i] == 1) cout << value[i] << " ";// 1  
            }
            cout << endl;
        }
        else
        {
            tmp[m] = 0;//         0，    
            subsetRecursive(value, m - 1, size);//      
            tmp[m] = 1;//         1，   
            subsetRecursive(value, m - 1, size);//      
        }
    }
    void subset(int *value, int size)
    {
        if (value == NULL || size < 1) return;//     
        createArray(size);
        subsetRecursive(value, size - 1, size);//      
        deleteArray();
    }
};

결 과 는 그림 과 같다.