parte3.c

#include <stdio.h>


int main ()
{
    int n, k;
    int limite = 1;
    int v[1000], subconjunto[1000];
    int i, j, l, contador_subconjunto, soma;
    int encontrou = 0;

    printf("Informe n:\n");
    scanf("%d", &n);

    printf("Informe os números:\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &v[i]);
    }
    
    // Tem que ordenar em ordem decrescente depois de ler o vetor ;)
    // Coloque aqui a rotina de ordenação do vetor que você fez, lembre-se que tem que estar em ordem decrescente \o/

    printf("Informe k:\n");
    scanf("%d", &k);

    /**
     * Explicando mais ou menos minha ideia:
     *
     * Eu tenho o limite que começa em 1. Essa variável limite, você pode pensar em outro nome pra ela, vou explicar o que ela é:
     *
     *      Trata-se da quantidade de números que serão somados no subconjuntos. Ele começa em 1 e depois vai aumentando, saca? q Até no máximo n.
     *
     *      Se n for 7, primeiro ele tenta casar com o limite 1, depois com o limite 2, depois 3, e assim sucessivamente.
     *      É essa a variável que da a segurança de encontrar sempre o menor subconjunto possível.
     *
     *  Esse while é o que controla a porra toda. Existem duas condições possíveis para sair desse loop:
     *
     *      1. O limite ser maior que n, ou seja, fez todas as combinações possíveis e não encontrou ninguém;
     *      2. A variável "encontrou" tem valor diferente de 0. A variável encontrou é uma variável de controle, caso o subconjunto seja encontrado com um elemento apenas, por exemplo, ela que garante que o while vai ser finalizado antes de testar todas as possibilidades.
     */
    while (limite <= n && !encontrou) {

        /**
         * Logo depois do while, vem o for que percorrerá todos os elementos.
         *
         * Se v for igual a [7, 4, 3, 2], por exemplo, ele vai pegar o 7 e montar todas as possibilidades, depois vai pegar o 4, depois o 3 e depois 2 (por isso a necessidade de estar em ordem decrescente, a lógica poderia ser repensada para aceitar qualquer ordem, mas com essa lógica, só funciona se tiver em ordem decrescente q)
         */
        for (j = 0; j < n && !encontrou; j++) {

            // O contador_subconjunto é zerado a cada iteração para que o vetor subconjunto seja reescrito a cada valor do vetor v
            contador_subconjunto = 0;

            // A soma também é zerada a cada iteração
            soma = 0;

            /**
             * Aqui o for que faz a soma.
             *
             * Veja que ele não percorre o vetor v inteiro: na verdade, ele começa em j, que é a posição atual do vetor, e vai até limite.
             *
             * Por exemplo, se o vetor for [7, 4, 3, 2], j = 2 e limite = 4, ele vai somar o subconjunto [4, 3], ou seja, no final da iteração, teremos:
             *
             *      soma == 7
             *      subconjunto == [4, 3]
             *
             */
            for (l = j; l < limite; l++) {
                soma += v[l];
                subconjunto[contador_subconjunto] = v[l];
                contador_subconjunto++;
            }

            /**
             * Por fim, pega a variável soma, que foi calculada no for anterior, e verifica se ela é maior ou igual a k.
             *
             * Se for, muda o valor da variável de controle encontro para 1 (que seria true, caso c tivesse suporte a tipos booleanos) e chama o comando break, que interrompe o for, impedindo que o próximo que a variável j avance para o próximo elemento da lista.
             *
             * Caso a soma seja menor que k, simplesmente continua o for, mudando o valor da variável j para o próximo elemento do vetor v.
             */
            if (soma >= k) {
                encontrou = 1;
            }
        }

        // Aqui ele incrementa o limite, ou seja, avança para o próximo tamanho de possíveis subconjuntos
        limite++;
    }

    // Aqui é bem simples: se encontrou é diferente de zero, vai escrever sim e o subconjunto
    // Caso contrário, só escreve não.
    if (encontrou) {
        printf("Sim.\n");
        for (i = 0; i < contador_subconjunto; i++) {
            printf("%d\n", subconjunto[i]);
        }
        printf("\n");
    } else {
        printf("Não.\n");
    }

    return 0;
}